Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 556 with 22 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 556 # by problem number
lcpy gen -s next_greater_element_iii # by problem name
n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive integer exists, return -1.
Note that the returned integer should fit in 32-bit integer, if there is a valid answer but it does not fit in 32-bit integer, return -1.
Input: n = 12
Output: 21
Input: n = 21
Output: -1
1 <= n <= 2^31 - 1MAX_32_BIT = 2**31 - 1
class Solution:
# Time: O(d) where d is the number of digits in n
# Space: O(d)
def next_greater_element(self, n: int) -> int:
digits = list(str(n))
length = len(digits)
# Find the rightmost index where digits[i] < digits[i + 1].
pivot = length - 2
while pivot >= 0 and digits[pivot] >= digits[pivot + 1]:
pivot -= 1
if pivot < 0:
return -1
# Smallest digit to the right of pivot that is still larger than it.
successor = length - 1
while digits[successor] <= digits[pivot]:
successor -= 1
digits[pivot], digits[successor] = digits[successor], digits[pivot]
# The suffix is non-increasing; reverse it to make it the smallest.
digits[pivot + 1 :] = reversed(digits[pivot + 1 :])
result = int("".join(digits))
return result if result <= MAX_32_BIT else -1
| Time | Space |
|---|---|
| O(d) where d is the number of digits in n | O(d) |