556. Next Greater Element III
Problem Description
Given a positive integer n
, the goal is to find the smallest integer greater than n
which contains exactly the same digits as n
. This number is essentially the next permutation in a lexicographically greater order of the digits. If there is no such number that is greater than n
with the same digits, the function returns -1
. Additionally, the answer must fit within a signed 32-bit integer. If the smallest integer is greater than what a 32-bit integer can represent, the function should also return -1
.
Intuition
The intuition behind the solution involves thinking about what makes one number bigger than another when they have the same digits. The key insight here is that for a number to be just bigger than the given number, the change must be made rightmost such that the digits to the right of this change-point are reversed to form the smallest sequence possible, while creating a number that is bigger than the original number.
-
Identify the rightmost digit that can be swapped to make the number bigger. We start from the right and look for the first digit that is smaller than the digit immediately to its right. If no such digit exists, the digits are in descending order and we cannot form a greater number, hence return
-1
. -
Swap the identified digit with the smallest digit to its right that is greater than itself. This guarantees that the increase in the number is as small as possible while still being greater than the original number.
-
Reverse the sequence to the right of the original change point. After the swap, the digits to the right of the change point are still in descending order. Reversing them will give us the smallest possible sequence to ensure that the overall number is the smallest possible number greater than
n
.
Implementing this approach, we can navigate through the digit sequence obtained from the integer n
and incrementally build up our solution step by step until we determine the next greatest element or lack thereof.
Learn more about Math and Two Pointers patterns.
Solution Approach
The solution uses a single-pass approach and the concept of rearranging the digits to form the next permutation. To walk through the algorithm:
-
Convert the integer
n
to a list of characters,cs
, to facilitate the swapping of digits. -
First, we iterate through
cs
from right to left, trying to find the first pair of digits where the left digit is less than the right digit. This step essentially finds the digit (cs[i]
) that can be swapped to create a number larger thann
. The loop variablei
starts from the second to last index (n-2
) and decreases. -
If such a digit
cs[i]
can't be found andi
becomes less than 0, it means that the digits are in descending order, and no greater number can be formed, hence we return-1
. -
Now that we have found the swap position at index
i
, we need to find the smallest digit greater thancs[i]
to its right. We do this by iterating from the end ofcs
until we find a digitcs[j]
that is greater. -
Swap
cs[i]
withcs[j]
to form a larger number. However, the digits to the right of indexi
are still in descending order, which would make the number larger than necessary. -
Reverse the sublist
cs[i+1:]
so that we get the smallest possible number that is larger thann
after the swap. -
Combine the characters back to form an integer
ans
and check if it is within the 32-bit integer range. Ifans
is larger than2**31 - 1
, which is the maximum value for a 32-bit signed integer, return-1
. -
Finally, if
ans
is within the range, return it. This result is now the smallest integer larger thann
using its digits.
This solution uses the pattern of finding the next permutation which is a well-known technique that applies to not just numbers but also arrays and sequences where you want to find a lexicographically ordered element.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use the integer n = 1423
as a small example to illustrate the solution approach.
-
Convert the integer
n
to a list of characterscs
, son = 1423
becomescs = ['1', '4', '2', '3']
. -
Iterate from right to left to find the first digit that is smaller than the digit immediately to its right. In our example, starting from the right, we compare
3
to2
,2
to4
, and then4
to1
. The first digit that is smaller than the digit to its right is2
. -
The swap position is found at index
i
wherecs[i] = '2'
. Now, find the smallest digit greater than'2'
to its right. This would be'3'
. -
Swap
cs[i]
withcs[j]
wherecs[j]
is'3'
. The listcs
now becomes['1', '3', '2', '4']
. -
The digits to the right of index
i
are['2', '4']
. We reverse this sublist to get the smallest sequence, which will result in['1', '3', '4', '2']
. -
Combine the characters to form the new integer
ans = 1342
. -
Check if
ans
fits within a signed 32-bit integer range. Sinceans = 1342
is less than2**31 - 1
, it is within the range. -
Return
ans
as the result. So the smallest integer greater than1423
containing the same digits is1342
.
Following this algorithm provides a simple and efficient method to determine the next permutation of an integer with the same set of digits.
Solution Implementation
1class Solution:
2 def nextGreaterElement(self, num: int) -> int:
3 # Convert the number to a list of characters for easy manipulation
4 char_list = list(str(num))
5 length = len(char_list)
6
7 # Start from the second last element and move backward to find the first element which is smaller than its next element
8 i = length - 2
9 while i >= 0 and char_list[i] >= char_list[i + 1]:
10 i -= 1
11
12 # If we can't find such an element, it means the number cannot be greater in its permutation
13 if i < 0:
14 return -1
15
16 # Now find an element which is greater than the found element at i
17 j = length - 1
18 while char_list[i] >= char_list[j]:
19 j -= 1
20
21 # Swap these two elements
22 char_list[i], char_list[j] = char_list[j], char_list[i]
23
24 # Reverse the sublist after the index i to get the next greater element in terms of permutation
25 char_list[i + 1 :] = char_list[i + 1:][::-1]
26
27 # Convert the char list back to an integer
28 next_greater = int(''.join(char_list))
29
30 # If the next greater number is bigger than the largest 32-bit integer, return -1
31 return next_greater if next_greater <= 2**31 - 1 else -1
32
1class Solution {
2 public int nextGreaterElement(int n) {
3 // Convert the integer to a char array for easy manipulation of digits
4 char[] digits = String.valueOf(n).toCharArray();
5 int length = digits.length;
6
7 // Start from the second last digit and move left until you find a digit
8 // that is less than its immediate right digit.
9 int i = length - 2;
10 while (i >= 0 && digits[i] >= digits[i + 1]) {
11 i--;
12 }
13
14 // If no such digit is found, no greater permutation exists.
15 if (i < 0) {
16 return -1;
17 }
18
19 // Start from the end of the array and move left until you find a digit
20 // that is greater than the digit found above.
21 int j = length - 1;
22 while (digits[i] >= digits[j]) {
23 j--;
24 }
25
26 // Swap the two digits found above.
27 swap(digits, i, j);
28
29 // Reverse the digits to the right of the position where the swap was made
30 // to get the next greater permutation with the smallest increase.
31 reverse(digits, i + 1, length - 1);
32
33 // Convert the resultant char array back to long to check for integer overflow.
34 long result = Long.parseLong(new String(digits));
35
36 // If the result is greater than the max value for int,
37 // return -1, otherwise, cast to int and return.
38 return result > Integer.MAX_VALUE ? -1 : (int) result;
39 }
40
41 // Helper method to swap two elements in a char array.
42 private void swap(char[] array, int i, int j) {
43 char temp = array[i];
44 array[i] = array[j];
45 array[j] = temp;
46 }
47
48 // Helper method to reverse a part of the char array between two indices.
49 private void reverse(char[] array, int start, int end) {
50 while (start < end) {
51 swap(array, start, end);
52 start++;
53 end--;
54 }
55 }
56}
57
1class Solution {
2public:
3 int nextGreaterElement(int n) {
4 // Convert the given integer to a string to manipulate individual digits.
5 string numStr = to_string(n);
6
7 // Get the length of the string representation of the integer.
8 int length = numStr.size();
9
10 // Initialize i for scanning the string from the right, starting at the second last digit.
11 int i = length - 2;
12
13 // Initialize j to point at the last digit of the number.
14 int j = length - 1;
15
16 // Find the first digit (scanning from right to left) that is smaller than the digit to its right.
17 while (i >= 0 && numStr[i] >= numStr[i + 1]) {
18 --i;
19 }
20
21 // If no such digit is found, the number cannot be made greater, return -1.
22 if (i < 0) return -1;
23
24 // Find the rightmost digit that is greater than numStr[i], starting from the end of the string.
25 while (numStr[i] >= numStr[j]) {
26 --j;
27 }
28
29 // Swap the digits at index i and j.
30 swap(numStr[i], numStr[j]);
31
32 // Reverse the substring starting from the digit next to index i to the end of the string.
33 // This gives us the next greater permutation of the number.
34 reverse(numStr.begin() + i + 1, numStr.end());
35
36 // Convert the modified string back to a long integer.
37 long ans = stol(numStr);
38
39 // Return the answer if it's within the range of a 32-bit integer,
40 // otherwise return -1.
41 return ans > INT_MAX ? -1 : static_cast<int>(ans);
42 }
43};
44
1// TypeScript function to find the next greater permutation of a given integer.
2function nextGreaterElement(n: number): number {
3 // Convert the given integer 'n' to a string to manipulate individual digits.
4 let numStr: string = n.toString();
5
6 // Initialize 'i' for scanning the string from the right, starting at the second last digit.
7 let i: number = numStr.length - 2;
8
9 // Find the first digit (scanning from right to left) that is smaller than the digit to its right.
10 while (i >= 0 && numStr.charAt(i) >= numStr.charAt(i + 1)) {
11 i--;
12 }
13
14 // If no such digit is found, the number cannot be made greater, return -1.
15 if (i < 0) return -1;
16
17 // Initialize 'j' to point at the last digit of the number.
18 let j: number = numStr.length - 1;
19
20 // Find the rightmost digit that is greater than numStr[i], starting from the end of the string.
21 while (numStr.charAt(i) >= numStr.charAt(j)) {
22 j--;
23 }
24
25 // Swap the digits at index 'i' and 'j'. We create a character array for swapping.
26 let numChars: string[] = numStr.split('');
27 [numChars[i], numChars[j]] = [numChars[j], numChars[i]]; // Perform the swap.
28 numStr = numChars.join(''); // Convert the character array back to a string.
29
30 // Reverse the substring starting from the digit next to index 'i' to the end of the string.
31 let toReverse: string = numStr.substring(i + 1);
32 let reversed: string = toReverse.split('').reverse().join('');
33 numStr = numStr.substring(0, i + 1) + reversed; // Concatenate the non-reversed and reversed parts.
34
35 // Convert the modified string back to an integer.
36 let ans: number = parseInt(numStr);
37
38 // Return the answer if it's within the range of a 32-bit integer; otherwise, return -1.
39 return ans > 2**31 - 1 ? -1 : ans;
40}
41
Time and Space Complexity
Time Complexity
The time complexity of this code is O(n)
, where n
is the number of digits in the given integer. Here's the breakdown of the time complexity:
- Converting the integer to a list of characters: This is done in
O(n)
time. - Finding the pivot point (
i
) such thatcs[i]
is just less than the element to its right (cs[i + 1]
): In the worst case, we may have to scan the entire list of digits from right to left, which is done inO(n)
time. - Finding the smallest digit greater than
cs[i]
to its right to swap with (j
): Again, in the worst-case scenario, this is done inO(n)
time. - Swapping
cs[i]
andcs[j]
: This is done in constant time,O(1)
. - Reversing the sublist after the pivot point: The sublist is at most
n - 1
elements long and reversing it is done inO(n)
. - Joining the list into a string and converting back to an integer: This operation is performed in
O(n)
time. - The final check to ensure the answer is within a 32-bit integer range is performed in constant time,
O(1)
.
All other operations are constant with respect to the size of the input and, as such, do not change the overall O(n)
complexity.
Space Complexity
The space complexity of the code is also O(n)
, where 'n' is the number of digits in the given integer. This is because:
- We store the list of characters,
cs
, which takesO(n)
space. - The additional space used when creating the sublist and reversing it also does not exceed
O(n)
.
There are no recursive calls or additional data structures that depend on the size of the input which would increase the space complexity further.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the minimum element can be found in:
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!