Next Greater Element III

Medium
386.

Next Greater Element III

Next Greater Element III is a medium coding problem on strings, math and two pointers, asked in Amazon, Google and Microsoft interviews.

Given a positive integer n, find the smallest integer that uses exactly the same digits and is greater than n.

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

Example 1

Input
n = 12
Output
21

Example 2

Input
n = 21
Output
-1

Example 3

Input
n = 230241
Output
230412

Constraints

  • 1 <= n <= 2147483647
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var nextGreaterElement = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Next Greater Element III — Solution in Python, Java & C++

Next Greater Element III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Next Greater Element III is a medium coding problem on strings, math and two pointers, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Strings, Math, Two Pointers
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a positive integer n, find the smallest integer that uses exactly the same digits and is greater than n.

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

Example 1

Input: n = 12
Output: 21

Example 2

Input: n = 21
Output: -1

Example 3

Input: n = 230241
Output: 230412

Constraints

  • 1 <= n <= 2147483647

Hints for Next Greater Element III

  1. Hint 1

    This is the "next permutation" algorithm applied to the digit string.

  2. Hint 2

    Scan from the right for the first digit smaller than its successor — that is the pivot.

  3. Hint 3

    Swap it with the smallest digit to its right that still exceeds it, then reverse everything after the pivot; finally check the 32-bit bound.

How to solve Next Greater Element III

Next permutation on the digit string: find the pivot from the right, swap it with the smallest larger digit after it, reverse the suffix, then check the 32-bit bound.

Approach

  1. Find the rightmost i with d[i] < d[i+1]; return -1 if none.
  2. Find the rightmost j > i with d[j] > d[i] and swap.
  3. Reverse d[i+1:] and rebuild the number, returning -1 if it exceeds 2³¹ - 1.

Why it works

The suffix after the pivot is the largest arrangement of its digits, so the next number must raise the pivot minimally and then minimise the suffix, which is what the swap-and-reverse does.

Complexity

  • Time — O(digits)
  • Space — O(digits)

Pitfalls

  • The overflow check must happen even though the input fits.

Reference solution

Python

def nextGreaterElement(n: int) -> int:
    digits = [int(c) for c in str(n)]
    i = len(digits) - 2
    while i >= 0 and digits[i] >= digits[i + 1]:
        i -= 1
    if i < 0:
        return -1
    j = len(digits) - 1
    while digits[j] <= digits[i]:
        j -= 1
    digits[i], digits[j] = digits[j], digits[i]
    digits[i + 1:] = reversed(digits[i + 1:])
    value = 0
    for d in digits:
        value = value * 10 + d
        if value > 2147483647:
            return -1
    return value

Java

public static int nextGreaterElement(int n) {
    char[] digits = String.valueOf(n).toCharArray();
    int i = digits.length - 2;
    while (i >= 0 && digits[i] >= digits[i + 1]) i--;
    if (i < 0) return -1;
    int j = digits.length - 1;
    while (digits[j] <= digits[i]) j--;
    char t = digits[i];
    digits[i] = digits[j];
    digits[j] = t;
    int lo = i + 1, hi = digits.length - 1;
    while (lo < hi) {
        char u = digits[lo];
        digits[lo] = digits[hi];
        digits[hi] = u;
        lo++;
        hi--;
    }
    long value = 0;
    for (char c : digits) {
        value = value * 10 + (c - '0');
        if (value > 2147483647L) return -1;
    }
    return (int) value;
}

C++

int nextGreaterElement(int n) {
    string digits = to_string(n);
    int i = (int) digits.size() - 2;
    while (i >= 0 && digits[i] >= digits[i + 1]) i--;
    if (i < 0) return -1;
    int j = (int) digits.size() - 1;
    while (digits[j] <= digits[i]) j--;
    swap(digits[i], digits[j]);
    reverse(digits.begin() + i + 1, digits.end());
    long long value = 0;
    for (char c : digits) {
        value = value * 10 + (c - '0');
        if (value > 2147483647LL) return -1;
    }
    return (int) value;
}

JavaScript

var nextGreaterElement = function(n) {
    const digits = String(n).split("").map(Number);
    let i = digits.length - 2;
    while (i >= 0 && digits[i] >= digits[i + 1]) i--;
    if (i < 0) return -1;
    let j = digits.length - 1;
    while (digits[j] <= digits[i]) j--;
    const t = digits[i];
    digits[i] = digits[j];
    digits[j] = t;
    const tail = digits.slice(i + 1).reverse();
    const out = digits.slice(0, i + 1).concat(tail);
    let value = 0;
    for (let k = 0; k < out.length; k++) {
        value = value * 10 + out[k];
        if (value > 2147483647) return -1;
    }
    return value;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Two Pointers Technique