Leetcode 556. Next Greater Element III
Problem Explanation:
The problem asks us to find the next largest number, which is a permutation of the given positive integer. If we played around with the digits of some numbers, we can easily find that if any digit that is not the left most one is larger than its left digit, then we can perform a swap operation to get a larger number. To get the smallest viable larger number, we need to swap it with the smallest possible digit on the right. If no suitable digit is found to perform the swap operation, return -1.
Let's take 12345 as an example. Here 5 is greater than 4 so we can swap it. But also 4 is greater than 3, so we can swap with that. We can repeat this process until we reach the start. This leaves us with 21345 after swapping 2 and 1.
Python Solution:
1 2python 3class Solution: 4 def nextGreaterElement(self, n: int) -> int: 5 number_str = list(str(n)) 6 m = len(number_str) 7 for idx in range(m-1, 0, -1): 8 if number_str[idx] > number_str[idx-1]: 9 for idx2 in range(m-1, -1, -1): 10 if number_str[idx2] > number_str[idx-1]: 11 number_str[idx-1], number_str[idx2] = number_str[idx2], number_str[idx-1] 12 number_str[idx:] = reversed(number_str[idx:]) 13 next_num = int(''.join(number_str)) 14 if next_num < (1 << 31): return next_num 15 return -1
Java Solution:
1 2java 3class Solution { 4 public int nextGreaterElement(int n) { 5 char[] number = (n + "").toCharArray(); 6 7 int i, j; 8 for (i = number.length - 1; i > 0; i--) { 9 if (number[i - 1] < number[i]) break; 10 } 11 12 if (i == 0) return -1; 13 14 for (j = number.length - 1; j >= i; j--) { 15 if (number[j] > number[i - 1]) break; 16 } 17 18 swap(number, i - 1, j); 19 reverse(number, i, number.length - 1); 20 long res = Long.parseLong(new String(number)); 21 22 return res <= Integer.MAX_VALUE ? (int) res : -1; 23 } 24 25 private void swap(char[] number, int i, int j) { 26 char temp = number[i]; 27 number[i] = number[j]; 28 number[j] = temp; 29 } 30 31 private void reverse(char[] number, int i, int j) { 32 while (i < j) { 33 swap(number, i, j); 34 i++; 35 j--; 36 } 37 } 38}
JavaScript Solution:
1 2javascript 3/** 4 * @param {number} n 5 * @return {number} 6 */ 7var nextGreaterElement = function(n) { 8 const arr = Array.from(n.toString()); 9 10 let i = arr.length - 2; 11 while (arr[i] >= arr[i + 1]) { 12 i--; 13 } 14 15 if (i === -1) { 16 return -1; 17 } 18 19 let j = arr.length - 1; 20 while (arr[j] <= arr[i]) { 21 j--; 22 } 23 24 swap(arr, i, j); 25 reverse(arr, i + 1, arr.length - 1); 26 27 const res = parseInt(arr.join('')); 28 29 return res <= ((1 << 31) - 1) ? res : -1; 30}; 31 32function swap (arr, i, j) { 33 const temp = arr[i]; 34 arr[i] = arr[j]; 35 arr[j] = temp; 36} 37 38function reverse (arr, i, j) { 39 while (i < j) { 40 swap(arr, i++, j--); 41 } 42}
C++ Solution:
1 2cpp 3class Solution { 4public: 5 int nextGreaterElement(int n) { 6 string num = to_string(n); 7 8 int i, j; 9 for (i = num.size() - 1; i > 0; i--) { 10 if (num[i - 1] < num[i]) break; 11 } 12 13 if (i == 0) return -1; 14 15 for (j = num.size() - 1; j >= i; --j) { 16 if (num[j] > num[i - 1]) break; 17 } 18 19 swap(num[i - 1], num[j]); 20 reverse(num.begin() + i, num.end()); 21 long res = stol(num); 22 23 return res <= INT_MAX ? (int) res : -1; 24 } 25};
C# Solution:
1 2csharp 3public class Solution { 4 public int NextGreaterElement(int n) { 5 string num = n.ToString(); 6 7 char[] number = num.ToCharArray(); 8 9 int i, j; 10 for (i = number.Length - 1; i > 0; i--) { 11 if (number[i - 1] < number[i]) break; 12 } 13 14 if (i == 0) return -1; 15 16 for (j = number.Length - 1; j >= i; j--) { 17 if (number[j] > number[i - 1]) break; 18 } 19 20 Swap(ref number[i - 1], ref number[j]); 21 Array.Reverse(number, i, number.Length - i); 22 long res = long.Parse(new string(number)); 23 24 return res <= int.MaxValue ? (int) res : -1; 25 } 26 27 public void Swap(ref char x, ref char y) { 28 char temp = x; 29 x = y; 30 y = temp; 31 } 32}
In all solutions above, first we transform the integer into a string for easier index access and comparisons. We scan the string from right to left and find the first pair of adjacent digits that is non-decreasing. Then we swap the smaller digit with the smallest digit that is on its right and greater than it. After the swap operation, sort the substring that is on the right of this digit. If we can't find a suitable digit to swap, return -1. Finally, we convert string back to an integer, ensuring it does not exceed the 32-bit integer limit.These solutions apply the same logic to the problem but use different language-specific implementations:
-
Python uses list comprehension and slicing to reverse the substring, a slice assignment to swap the digits and checks the existence of overflow by comparing the result with
(1 << 31)
. If the result is greater than(1 << 31)
, it returns -1, else, it returns the result. -
The Java solution uses built-in functions
swap()
andreverse()
. If an overflow exists, the solution checks whether thelong
result is greater thanInteger.MAX_VALUE
. If the result is greater thanInteger.MAX_VALUE
, it returns -1, else, it returns the result as an integer. -
JavaScript makes use of the built-in
reverse()
method to reverse the order of the digits in the array from the given start index up to, but not including, the end index. It checks if the number is within the JavaScript safe integer limit(1 << 31) - 1
before returning the result. -
In the C++ solution, it first converts the number to a string, then uses algorithm library functions
swap()
andreverse()
to perform the operations. For checking the overflow, it uses C++ built-inINT_MAX
. -
The C# solution uses,
Array.Reverse()
to reverse digits in the array and has an explicit function to swap two characters in the char array. It checks if the result number is greater thanint.MaxValue
to handle an overflow scenario.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.