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 than n. The loop variable i starts from the second to last index (n-2) and decreases.
If such a digit cs[i] can't be found and i 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 than cs[i] to its right. We do this by iterating from the end of cs until we find a digit cs[j] that is greater.
Swap cs[i] with cs[j] to form a larger number. However, the digits to the right of index i 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 than n after the swap.
Combine the characters back to form an integer ans and check if it is within the 32-bit integer range. If ans is larger than 2**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 than n 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 Evaluator

Example 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 characters cs, so n = 1423 becomes cs = ['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 to 2, 2 to 4, and then 4 to 1. The first digit that is smaller than the digit to its right is 2.
The swap position is found at index i where cs[i] = '2'. Now, find the smallest digit greater than '2' to its right. This would be '3'.
Swap cs[i] with cs[j] where cs[j] is '3'. The list cs 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. Since ans = 1342 is less than 2**31 - 1, it is within the range.
Return ans as the result. So the smallest integer greater than 1423 containing the same digits is 1342.

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 that cs[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 in O(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 in O(n) time.
Swapping cs[i] and cs[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 in O(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 takes O(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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know