Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.

Example 1:


Input: 12
Output: 21


 

Example 2:


Input: 21
Output: -1

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Amortized analysis

Mathematics

Starter code: class Solution:
    def nextGreaterElement(self, n: int) -> int:
        

Solutions:
class Solution:

	def nextGreaterElement(self, n):
		s = [i for i in str(n)]
		exist = -1
		for i in range(len(s) - 1, 0, -1):
			if s[i - 1] < s[i]:
				temp = sorted(s[i - 1:])
				pivot = temp.index(s[i - 1])
				for j in range(pivot + 1, len(temp)):
					if temp[j] > s[i - 1]:
						pivot = j
						break
				s[i - 1] = temp[pivot]
				del temp[pivot]
				s[i:] = temp
				exist = 1
				break
		ret = int(''.join(s))
		if exist == 1 and ret < 2147483647:
			return ret
		else:
			return -1


class Solution:

	def nextGreaterElement(self, n):
		sn = str(n)
		nlen = len(sn)
		if nlen == 1:
			return -1
		else:
			(i, j) = (-1, -2)
			(end, check) = (i, True)
			sl = list(sn)
			while j != -nlen and sl[j] >= sl[i]:
				if sl[end] < sl[j] and check:
					end = j
					check = False
				i -= 1
				j -= 1
			if sl[j] == sl[end]:
				if i > j:
					end = i
			if sl[j] == min(sl):
				end = -1
			(sl[j], sl[end]) = (sl[end], sl[j])
			(front, back) = (sl[:j + 1], sorted(sl[j + 1:]))
			result = int(''.join(front + back))
			return result if result > n and result < 2147483647 else -1


class Solution:

	def nextGreaterElement(self, n):
		nn = str(n)
		l = len(nn)
		if l < 2:
			return -1
		x = -1
		for i in range(l - 1, 0, -1):
			if nn[i] > nn[i - 1]:
				x = i - 1
				break
		if x == -1:
			return -1
		y = nn[x + 1]
		yy = x + 1
		for i in range(x + 1, l):
			if nn[i] > nn[x]:
				y = min(y, nn[i])
				if y == nn[i]:
					yy = i
		left = nn[:x] + y
		right = nn[yy + 1:l] + nn[x] + nn[x + 1:yy]
		res = int(left + ''.join(sorted(right)))
		return res if res < 2 ** 31 else -1


class Solution:

	def nextGreaterElement(self, n):
		digits = list(map(int, list(str(n))))
		last = None
		for i in range(0, len(digits) - 1):
			if digits[i + 1] > digits[i]:
				last = i
		if last == None:
			return -1
		rst = ''
		i = last
		for j in range(0, i):
			rst += str(digits[j])
		p = digits[i]
		for x in range(p + 1, 10):
			if x in digits[i + 1:]:
				break
		rst += str(x)
		used = False
		for p in sorted([digits[i]] + digits[i + 1:]):
			if p == x and (not used):
				used = True
			else:
				rst += str(p)
		f = int(rst)
		if f > 2147483647:
			return -1
		else:
			return f


class Solution:

	def nextGreaterElement(self, n):
		nums = list(str(n))
		size = len(nums)
		for i in range(size - 1, -1, -1):
			if nums[i - 1] < nums[i]:
				break
		if i > 0:
			for j in range(size - 1, -1, -1):
				if nums[j] > nums[i - 1]:
					(nums[i - 1], nums[j]) = (nums[j], nums[i - 1])
					break
		for k in range((size - i) // 2):
			(nums[i + k], nums[size - k - 1]) = (nums[size - k - 1], nums[i + k])
		ans = int(''.join(nums))
		return n < ans <= 2147483647 and ans or -1


class Solution:

	def nextGreaterElement(self, n):
		s = str(n)
		l = len(s)
		digits = [int(c) for c in s]
		i = l - 1
		while i > 0 and s[i] <= s[i - 1]:
			i -= 1
		if i == 0:
			return -1
		j = l - 1
		while j > i - 1 and s[j] <= s[i - 1]:
			j -= 1
		(digits[i - 1], digits[j]) = (digits[j], digits[i - 1])
		res = digits[:i] + sorted(digits[i:])
		res = int(''.join((str(d) for d in res)))
		if res > 2 ** 31:
			return -1
		return res