Log inSign up
mediumLeetCodeNot Started

Next Greater Element III

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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 · Standard Two-Digit Swap:

Input: n = 12
Output: 21
Explanation: Permutations of 12 are 12 and 21. Next greater is 21.

Example 2 · Strictly Decreasing Digits:

Input: n = 21
Output: -1
Explanation: 21 is the maximum possible arrangement of digits 1 and 2, so no greater integer exists.

Example 3 · 32-bit Integer Overflow:

Input: n = 2147483486
Output: -1
Explanation: Next permutation exists as digits but exceeds 231 - 1 (2147483647), so return -1.

Constraints:

  • 1 <= n <= 231 - 1

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Next Permutation algorithm
  • String to integer parsing and 32-bit overflow handling
  • Two-pointer array reversal

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Bridge array permutation algorithms (Next Permutation) to digit-level integer manipulation.
  • Master the 3-step Next Permutation algorithm: pivot -> successor swap -> suffix reverse.
  • Handle 32-bit signed integer overflow (INT_MAX = 2,147,483,647).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • Convert integer n to character/digit array.
  • Apply Next Permutation: (1) Find pivot i from right where s[i] < s[i+1], (2) Find successor j where s[j] > s[i], (3) Swap s[i], s[j], (4) Reverse s[i+1...end].
  • Check result <= INT_MAX; return result if valid, else -1.

Connected Patterns:

Next PermutationPrevious Permutation With One SwapNext Greater Element I

1. Increment and Digits Comparison (Brute Force)

Intuition

Count the frequency of each digit 0-9 in the number n. Increment candidate = n + 1, n + 2, ... and count digit frequencies. If the digit counts match, we found the smallest greater integer with identical digits. If candidate exceeds Integer.MAX_VALUE (2147483647), return -1.

When to apply: Use only for small numbers to understand the digit permutation requirement.

Brute Force Increment Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2]
Current operationSTEP 1 OF 6
Given n = 12
Visual state
Values and pointers at this exact step
array
S
1
2
0
↑ n=12
1
Variables at this step
n
12
digits
1,2
Check / comparison
n = 12
Decision / next transition
Test candidates starting from 13.
Why this step matters

Given n = 12. Digits: {1: 1, 2: 1}. Goal: find smallest number > 12 with digits 1 and 2.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int nextGreaterElement(int n) {
4 int[] count = getCount(n);
5 long cand = (long)n + 1;
6 while (cand <= Integer.MAX_VALUE) {
7 if (matches(count, getCount(cand))) {
8 return (int)cand;
9 }
10 cand++;
11 }
12 return -1;
13 }
14
15 private int[] getCount(long num) {
16 int[] c = new int[10];
17 while (num > 0) {
18 c[(int)(num % 10)]++;
19 num /= 10;
20 }
21 return c;
22 }
23
24 private boolean matches(int[] a, int[] b) {
25 for (int i = 0; i < 10; i++) {
26 if (a[i] != b[i]) return false;
27 }
28 return true;
29 }
30 }
31
32 public static void main(String[] args) {
33 Solution sol = new Solution();
34 int n = 12;
35 System.out.println("Next Greater Element: " + sol.nextGreaterElement(n));
36 }
37}

Time & Space Complexity

  • Time complexity: O(k * d) — Checking up to k integers where each integer takes d digit frequency checks takes O(k * d) time.
  • Space complexity: O(1) — O(1) auxiliary frequency arrays of fixed size 10.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Digit Permutations Generation (Better)

Intuition

Deconstruct the number n into its individual digits. Generate all distinct permutations of the digits. Sort them in ascending order and find the first permutation whose value is strictly greater than n. Verify that the value fits in a 32-bit signed integer.

When to apply: Use to understand the lexicographical next permutation ordering of digit multisets.

Permutations Lexicographical Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 3, 0, 2, 4, 1]
Current operationSTEP 1 OF 6
Digits of n = 230241: ['2', '3', '0', '2', '4', '1']
Visual state
Values and pointers at this exact step
array
S
2
3
0
2
4
1
0
↑ n
1
2
3
4
5
Variables at this step
n
230241
Check / comparison
Construct permutations.
Decision / next transition
Generate sorted unique values.
Why this step matters

Digits of n = 230241: [2, 3, 0, 2, 4, 1]. Length d = 6.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int nextGreaterElement(int n) {
6 char[] a = String.valueOf(n).toCharArray();
7 int i = a.length - 2;
8 while (i >= 0 && a[i] >= a[i + 1]) {
9 i--;
10 }
11 if (i < 0) return -1;
12 int j = a.length - 1;
13 while (a[j] <= a[i]) {
14 j--;
15 }
16 swap(a, i, j);
17 reverse(a, i + 1, a.length - 1);
18 try {
19 long val = Long.parseLong(new String(a));
20 return val > Integer.MAX_VALUE ? -1 : (int)val;
21 } catch (Exception e) {
22 return -1;
23 }
24 }
25
26 private void swap(char[] a, int i, int j) {
27 char t = a[i];
28 a[i] = a[j];
29 a[j] = t;
30 }
31
32 private void reverse(char[] a, int i, int j) {
33 while (i < j) swap(a, i++, j--);
34 }
35 }
36
37 public static void main(String[] args) {
38 Solution sol = new Solution();
39 int n = 12;
40 System.out.println("Next Greater Element: " + sol.nextGreaterElement(n));
41 }
42}

Time & Space Complexity

  • Time complexity: O(d! * d) — There are up to d! permutations of d digits, each taking O(d) to construct.
  • Space complexity: O(d! * d) — Storing all permutations in memory requires O(d! * d) space.

3. Next Permutation on Digits (Optimal)

Intuition

This problem is exactly the classic Next Permutation applied to the decimal digits of integer n: 1. Scan from right to left to find the first decrease: index i where digits[i] < digits[i+1]. If no such index exists, the digits are in descending order; no larger integer can be formed, return -1. 2. Scan from right to left to find the smallest digit greater than digits[i]: index j where digits[j] > digits[i]. 3. Swap digits[i] and digits[j]. 4. Reverse the suffix from i + 1 to the end to make it as small as possible. 5. Parse the number into a 64-bit integer; if it exceeds 231 - 1, return -1.

When to apply: Use as the optimal O(d) time, O(d) space solution (where d <= 10 is the number of digits).

Next Permutation Algorithm Interactive Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 1, 8, 7, 6, 5]
Current operationSTEP 1 OF 6
Step 1: Convert n = 218765 to digit array: ['2', '1', '8', '7', '6', '5']
Visual state
Values and pointers at this exact step
pointers
S
2
1
8
7
6
5
0
1
↑ Pivot i=1 ('1')
2
3
4
5
Variables at this step
i
1
pivotDigit
1
suffix
8,7,6,5
Check / comparison
Comparing adjacent digits backwards: 6 > 5, 7 > 6, 8 > 7, 1 < 8!
Decision / next transition
First drop found at index i = 1 (digit '1'). Suffix [8, 7, 6, 5] is descending.
Why this step matters

Step 1: Convert n = 218765 to digit array: [2, 1, 8, 7, 6, 5]. Scan from right to find first drop digits[i] < digits[i+1].

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int nextGreaterElement(int n) {
4 char[] a = String.valueOf(n).toCharArray();
5 int i = a.length - 2;
6 while (i >= 0 && a[i] >= a[i + 1]) {
7 i--;
8 }
9 if (i < 0) return -1;
10 int j = a.length - 1;
11 while (a[j] <= a[i]) {
12 j--;
13 }
14 char temp = a[i];
15 a[i] = a[j];
16 a[j] = temp;
17
18 int left = i + 1, right = a.length - 1;
19 while (left < right) {
20 char t = a[left];
21 a[left] = a[right];
22 a[right] = t;
23 left++;
24 right--;
25 }
26
27 long val = Long.parseLong(new String(a));
28 return val > Integer.MAX_VALUE ? -1 : (int)val;
29 }
30 }
31
32 public static void main(String[] args) {
33 Solution sol = new Solution();
34 int n = 12;
35 System.out.println("Next Greater Element: " + sol.nextGreaterElement(n));
36 }
37}

Time & Space Complexity

  • Time complexity: O(d) — The number of digits d is at most 10 for a 32-bit integer. The linear scans, swap, and reverse take O(d) time.
  • Space complexity: O(d) — O(d) auxiliary space to hold the digit characters of the integer.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Generate All PermutationsO(D! * D)O(D!)Generate all digit permutations, sort them, and pick the smallest one strictly greater than n.Generating all permutations.
2.Optimal — In-Place Next PermutationO(D)O(D)Find pivot from right, swap with successor, reverse suffix in linear time.None; industry-standard optimal solution.
3.Alternative — Counting DigitsOptimalO(D)O(10)Count digit frequencies of suffix from right to left, picking smallest larger digit.Extra bucket assembly.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Strictly decreasing digits (e.g. 321) -> No pivot exists, returns -1.
  • Single digit input (e.g. 5) -> Cannot form a greater number, returns -1.
  • 32-bit Integer overflow (e.g. 2147483486 -> next permutation exceeds 2147483647), must return -1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Next Greater Element III?

2.Why is the brute force approach suboptimal for large inputs in Next Greater Element III?

3.Which data structure or technique enables the optimal solution for Next Greater Element III?

Back to DSA Sheet