Next Greater Element III

Medium Arrays & Hashing Right to Left Traversal Original on LeetCode

Next Greater Element III is a medium arrays & hashing problem solved with the right to left traversal pattern. The best approach, optimal (next permutation of the digits), runs in O(d) time and O(d) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every arrangement) up.

Problem

Given a positive integer n, return the smallest integer greater than n that uses exactly the same digits as n (each digit the same number of times).

If no such integer exists, or the smallest one does not fit in a signed 32-bit integer, return -1.

Examples

Example 1

Input
n = 2763
Output
3267
Why
Among rearrangements of the digits 2, 7, 6, 3, the smallest one larger than 2763 is 3267.

Example 2

Input
n = 5310
Output
-1
Why
The digits are already in descending order, so no rearrangement is larger.

Example 3

Input
n = 2147483476
Output
2147483647
Why
The next arrangement still fits in a signed 32-bit integer (it is exactly the largest one).

Constraints

  • 1 <= n <= 2^31 - 1
  • Return -1 if no larger arrangement exists or if it does not fit in a signed 32-bit integer.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every arrangement)O(d! · d)O(d)
Optimal (next permutation of the digits)O(d)O(d)

1Brute force (try every arrangement)

TimeO(d! · d)Up to d! arrangements of the d ≤ 10 digits, each built in O(d).
SpaceO(d)The recursion depth and the used flags.

Generate every distinct arrangement of the digits with backtracking, convert each to a number, and keep the smallest one that is larger than n and still fits in 32 bits.

  1. Sort the digits; backtrack over unused positions, skipping a digit equal to its unused left neighbour to avoid duplicates.
  2. For each complete arrangement value v (as a long): if n < v <= 2^31 - 1, best = min(best, v).
  3. Return best, or -1 if none was found.
class Solution {
    private long best;
    private long target;

    public int nextGreaterElement(int n) {
        char[] digits = String.valueOf(n).toCharArray();
        Arrays.sort(digits);
        best = Long.MAX_VALUE;
        target = n;
        build(digits, new boolean[digits.length], 0, 0);
        return best == Long.MAX_VALUE ? -1 : (int) best;
    }

    private void build(char[] digits, boolean[] used, int depth, long value) {
        if (depth == digits.length) {
            if (value > target && value <= Integer.MAX_VALUE) best = Math.min(best, value);
            return;
        }
        for (int i = 0; i < digits.length; i++) {
            if (used[i]) continue;
            if (i > 0 && digits[i] == digits[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            build(digits, used, depth + 1, value * 10 + (digits[i] - '0'));
            used[i] = false;
        }
    }
}

2Optimal (next permutation of the digits)

TimeO(d)A constant number of passes over the d ≤ 10 digits.
SpaceO(d)The digit array.

Scan from the right for the first position i with d[i] < d[i + 1]; if none exists the digits are non-increasing and the answer is -1. Swap d[i] with the rightmost digit larger than it, then reverse the suffix after i so it becomes the smallest possible. Convert with a long and reject values above 2^31 - 1.

  1. d = digits of n; i = len - 2; while i >= 0 and d[i] >= d[i + 1], i--.
  2. If i < 0, return -1.
  3. j = len - 1; while d[j] <= d[i], j--. Swap d[i], d[j].
  4. Reverse d[i + 1 …]; parse as long; return it if <= 2^31 - 1, else -1.
class Solution {
    public int nextGreaterElement(int n) {
        char[] d = String.valueOf(n).toCharArray();
        int i = d.length - 2;
        while (i >= 0 && d[i] >= d[i + 1]) i--;
        if (i < 0) return -1;
        int j = d.length - 1;
        while (d[j] <= d[i]) j--;
        char t = d[i]; d[i] = d[j]; d[j] = t;
        for (int l = i + 1, r = d.length - 1; l < r; l++, r--) {
            t = d[l]; d[l] = d[r]; d[r] = t;
        }
        long value = Long.parseLong(new String(d));
        return value > Integer.MAX_VALUE ? -1 : (int) value;
    }
}

Edge cases to test

  • Single digit, or digits in non-increasing order: -1
  • Repeated digits, like 1221 or 115
  • The next arrangement exceeds 2^31 - 1 (for example 2147483486 → 2147483648): -1
  • Zeros in the number, like 1020

Hints

Hint 1

This is the next permutation of the digit sequence. Where does the rightmost change have to happen?

Hint 2

From the right, find the first digit that is smaller than the digit after it. Everything to its right is non-increasing.

Hint 3

Swap that digit with the smallest larger digit to its right, then reverse the suffix. Check the result against the 32-bit limit with a long.

FAQ

What is the best time complexity for Next Greater Element III?

Optimal (next permutation of the digits) runs in O(d) time and O(d) extra space. A constant number of passes over the d ≤ 10 digits.

Which pattern does Next Greater Element III use?

It is a arrays & hashing problem that uses the right to left traversal pattern. Other problems with the same pattern: Array Leaders, Product of Array Except Self, Next Permutation.

Is there a brute force solution for Next Greater Element III?

Yes. Brute force (try every arrangement) takes O(d! · d) time and O(d) space. Generate every distinct arrangement of the digits with backtracking, convert each to a number, and keep the smallest one that is larger than n and still fits in 32 bits.

Which edge cases should I test for Next Greater Element III?

Single digit, or digits in non-increasing order: -1; Repeated digits, like 1221 or 115; The next arrangement exceeds 2^31 - 1 (for example 2147483486 → 2147483648): -1; Zeros in the number, like 1020.