Next Greater Element III
MedPrompt
Given a positive integer 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.
Example 1:
Input: n = 12
Output: 21Example 2:
Input: n = 21
Output: -1
Constraints:
1 <= n <= 231 - 1
Approaches
2 approaches with complexity analysis and trade-offs.
This approach tackles the problem by generating all possible numbers that can be formed by rearranging the digits of the input number n. From this complete set of permutations, we filter to find all numbers that are strictly greater than n. The smallest number in this filtered set is our answer. If no such number exists, it means n is already the largest possible permutation of its digits.
Algorithm
- Convert the input integer
ninto a character array representing its digits. - Define a recursive function to generate all permutations of the digits. Use a
Setto store the unique numbers formed by these permutations to avoid duplicates. - In the recursive function:
- Base case: When a full permutation is formed (i.e., we've reached the end of the digit array), convert it to a
longand add it to the set. - Recursive step: Iterate through the remaining digits, swap the current digit with each of the others, and make a recursive call.
- Base case: When a full permutation is formed (i.e., we've reached the end of the digit array), convert it to a
- After generating all permutations, iterate through the set of numbers.
- Find the minimum number that is greater than the original
n. - If no such number is found, or if the found number is larger than
Integer.MAX_VALUE, return -1. - Otherwise, return the found number as an
int.
Walkthrough
The core of this method is a permutation generation algorithm. We first convert the integer n into an array of its digits. Then, we use a recursive function, typically employing backtracking, to generate every unique arrangement of these digits. Each permutation is converted back into a number. We maintain a list of all generated numbers that are larger than the original n. After exploring all permutations, we find the minimum value in this list. A special check is required to ensure the result does not exceed the 32-bit integer limit. If no greater number is found, or the smallest greater number overflows, we return -1.
import java.util.ArrayList;import java.util.Collections;import java.util.HashSet;import java.util.List;import java.util.Set; class Solution { public int nextGreaterElement(int n) { String s = String.valueOf(n); char[] digits = s.toCharArray(); Set<Long> permutations = new HashSet<>(); // Using a Set helps handle duplicate permutations automatically generatePermutations(digits, 0, permutations); long minGreater = Long.MAX_VALUE; boolean found = false; for (long p : permutations) { if (p > n) { minGreater = Math.min(minGreater, p); found = true; } } if (!found || minGreater > Integer.MAX_VALUE) { return -1; } return (int) minGreater; } private void generatePermutations(char[] digits, int index, Set<Long> permutations) { if (index == digits.length) { try { permutations.add(Long.parseLong(new String(digits))); } catch (NumberFormatException e) { // This case is unlikely given the constraints but good practice. } return; } // Generate permutations for the rest of the array for (int i = index; i < digits.length; i++) { swap(digits, index, i); generatePermutations(digits, index + 1, permutations); swap(digits, index, i); // backtrack } } private void swap(char[] arr, int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}Complexity
Time
O(d! * d), where `d` is the number of digits in `n`. For a 32-bit integer, `d` is at most 10. Generating `d!` permutations and converting each to a number of length `d` leads to this complexity.
Space
O(d! * d). We need to store up to `d!` permutations, each requiring `O(d)` space.
Trade-offs
Pros
Conceptually simple and directly follows the problem's definition of rearranging digits.
Guaranteed to find the correct answer if one exists (within computational limits).
Cons
Extremely inefficient due to factorial time complexity. Unsuitable for numbers with more than a few digits.
High memory consumption to store all generated permutations.
A highly efficient approach that avoids generating all permutations. It's based on the standard algorithm for finding the next lexicographically greater permutation of a sequence. By making a few targeted modifications to the sequence of digits, we can directly construct the smallest number that is larger than the input n.
Algorithm
- Convert the input integer
nto a character arraya. - Scan
afrom right to left to find the first indexisuch thata[i] < a[i+1]. This is the pivot. - If no such
iexists, all digits are in descending order. Return -1. - Scan
aagain from right to left (from the end toi+1) to find the first indexjwherea[j] > a[i]. - Swap the characters at indices
iandj. - Reverse the subarray of
afrom indexi+1to the end. - Convert the modified character array
aback to a number. Uselongto prevent premature overflow during parsing. - Check if the resulting number exceeds
Integer.MAX_VALUE. If it does, return -1. Otherwise, cast tointand return.
Walkthrough
The algorithm works by manipulating the digits of n as a character array. We scan the digits from right to left to find the first position i where the digit is smaller than the digit to its right (a[i] < a[i+1]). This digit a[i] is our 'pivot'. The suffix of the number starting from i+1 is in non-increasing (descending) order.
Next, we find the smallest digit in this suffix that is still larger than our pivot a[i]. We swap this digit with the pivot.
Finally, to ensure the resulting number is the smallest possible greater number, we reverse the suffix that starts after the pivot's original position. This arranges the remaining digits in ascending order. The resulting sequence of digits forms our answer, which we convert back to a number, checking for 32-bit integer overflow.
import java.util.Arrays; class Solution { public int nextGreaterElement(int n) { char[] a = String.valueOf(n).toCharArray(); int len = a.length; int i = len - 2; // Step 1: Find the first digit from the right that is smaller than the digit to its right. while (i >= 0 && a[i] >= a[i+1]) { i--; } // If no such digit is found, it means the digits are in descending order (e.g., 321). // This is the largest permutation, so no greater element exists. if (i < 0) { return -1; } // Step 2: Find the smallest digit to the right of a[i] that is greater than a[i]. int j = len - 1; while (j > i && a[j] <= a[i]) { j--; } // Step 3: Swap the pivot a[i] with a[j]. swap(a, i, j); // Step 4: Reverse the part of the array to the right of i to get the smallest permutation. reverse(a, i + 1); try { long val = Long.parseLong(new String(a)); if (val > Integer.MAX_VALUE) { return -1; } return (int) val; } catch (NumberFormatException e) { // This catch block handles cases where the number is too large for a long, // which is not possible given the constraints on n, but is good practice. return -1; } } private void swap(char[] a, int i, int j) { char temp = a[i]; a[i] = a[j]; a[j] = temp; } private void reverse(char[] a, int start) { int i = start, j = a.length - 1; while (i < j) { swap(a, i, j); i++; j--; } }}Complexity
Time
O(d), where `d` is the number of digits in `n`. The algorithm involves a few linear scans of the digit array, each taking `O(d)` time.
Space
O(d) to store the digits of the number in a character array.
Trade-offs
Pros
Extremely efficient, with a time complexity linear in the number of digits.
Minimal space usage.
Directly constructs the answer without generating unnecessary permutations.
Cons
The logic can be non-obvious and requires understanding the properties of lexicographical permutations.
Solutions
Solution
class Solution {public int nextGreaterElement(int n) { char[] cs = String.valueOf(n).toCharArray(); n = cs.length; int i = n - 2, j = n - 1; for (; i >= 0 && cs[i] >= cs[i + 1]; --i) ; if (i < 0) { return -1; } for (; cs[i] >= cs[j]; --j) ; swap(cs, i, j); reverse(cs, i + 1, n - 1); long ans = Long.parseLong(String.valueOf(cs)); return ans > Integer.MAX_VALUE ? -1 : (int)ans; }private void swap(char[] cs, int i, int j) { char t = cs[i]; cs[i] = cs[j]; cs[j] = t; }private void reverse(char[] cs, int i, int j) { for (; i < j; ++i, --j) { swap(cs, i, j); } }}class Solution {public: int nextGreaterElement(int n) { string s = to_string(n); n = s.size(); int i = n - 2, j = n - 1; for (; i >= 0 && s[i] >= s[i + 1]; --i) ; if (i < 0) return -1; for (; s[i] >= s[j]; --j) ; swap(s[i], s[j]); reverse(s.begin() + i + 1, s.end()); long ans = stol(s); return ans > INT_MAX ? -1 : ans; }};class Solution: def nextGreaterElement(self, n: int) -> int: cs = list(str(n)) n = len(cs) i, j = n - 2, n - 1 while i >= 0 and cs[i] >= cs[i + 1]: i -= 1 if i < 0: return - 1 while cs[i] >= cs[j]: j -= 1 cs[i], cs[j] = cs[j], cs[i] cs[i + 1:] = cs[i + 1:][:: - 1] ans = int('' . join(cs)) return - 1 if ans > 2 ** 31 - 1 else ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.