Next Greater Element III

Next Greater Element III

What is this problem about?

The Next Greater Element III problem gives you a positive integer n and asks you to find the smallest integer greater than n that uses the same digits as n. This is equivalent to finding the next permutation of n's digit sequence. If no such number exists or it overflows a 32-bit integer, return -1. This Next Greater Element III coding problem applies the next permutation algorithm to integer digits.

Why is this asked in interviews?

Goldman Sachs, Microsoft, Meta, Amazon, Google, and Bloomberg ask this because it applies the Next Permutation algorithm to a real-world scenario — rearranging digits to find the next larger number. The math, two pointers, and string interview pattern is directly applied, and the overflow check adds practical implementation detail.

Algorithmic pattern used

Next Permutation on digit array. Convert n to a digit string/array. Apply the next permutation algorithm: (1) find the rightmost digit that is smaller than the digit to its right (pivot); (2) find the rightmost digit greater than the pivot and swap them; (3) reverse the suffix after the pivot position. Convert back to integer. If no pivot found (digits are non-increasing), return -1. Check for 32-bit overflow.

Example explanation

n = 1243. Digits: [1, 2, 4, 3].

• Pivot: index 2 (digit 4 > 3, so step back: index 1, digit 2 < 4). Pivot at index 1.
• Rightmost digit > 2 in suffix [4,3]: that's index 2 (4). Swap → [1, 4, 2, 3].
• Reverse suffix after pivot [2,3] → [3,2]. Result: [1,4,3,2] = 1432.

Common mistakes candidates make

• Not handling the all-descending case (return -1, no next permutation).
• Incorrect pivot search (must find rightmost ascending pair from right).
• Forgetting to reverse the suffix (just swapping pivot doesn't complete the algorithm).
• Missing the 32-bit integer overflow check (compare to 2^31 - 1 before returning).

Interview preparation tip

Next Permutation is one of the most important two-pointer algorithms. The three-step pattern — find pivot, swap with next-greater, reverse suffix — is elegant and widely applicable. Memorize it until you can write it in under 2 minutes. Next Greater Element III adds the digit-extraction and overflow-check wrapper. Practice applying Next Permutation in different contexts: string permutations, number rearrangements, and sequence generation problems.