#556

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Next Greater Element III

Find the next greater integer using the same digits as a given number with precise two-pointer scanning and invariant tracking.

math two pointers string

Problem Statement

Given a positive integer n, determine the smallest integer that contains exactly the same digits as n and is strictly greater than n. If such an integer does not exist or exceeds the 32-bit signed integer range, return -1.

For example, if n = 12, the next greater integer using the same digits is 21. If n = 21, no greater integer can be formed, so the output is -1. The solution must handle integer bounds and correctly reorder digits to achieve the minimal next value.

Examples

Example 1

Input: n = 12

Output: 21

Example details omitted.

Example 2

Input: n = 21

Output: -1

Example details omitted.

Constraints

1 <= n <= 231 - 1

Solution Approach

Identify the pivot from the right

Scan the digits from right to left to find the first position where a digit is smaller than the digit immediately to its right. This pivot marks the location to increase the number minimally.

Swap with the smallest larger digit

Once the pivot is found, locate the smallest digit to its right that is greater than the pivot digit. Swap these two digits to begin forming the next greater integer while keeping changes minimal.

Reverse the suffix to finalize

After swapping, reverse all digits to the right of the pivot to achieve the smallest possible number greater than the original. This ensures the next permutation is minimal and respects two-pointer invariant scanning.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(k) where k is the number of digits in n due to single pass scans for pivot, swap, and reverse. Space complexity is O(k) for digit storage when performing swaps and reversals.

What Interviewers Usually Probe

Expect clear explanation of pivot selection and suffix reversal.
Look for careful handling of integer overflow with 32-bit constraints.
Candidate should articulate why two-pointer scanning ensures minimal increase.

Common Pitfalls or Variants

Common pitfalls

Failing to scan from the right and missing the correct pivot location.
Swapping with a digit that does not yield the minimal next number.
Ignoring 32-bit integer constraints leading to incorrect return values.

Follow-up variants

Next Greater Element II with circular array considerations.
Next smaller permutation of digits problem using similar two-pointer logic.
Handling inputs with repeated digits requiring careful pivot and swap selection.

FAQ

What is the main pattern used in Next Greater Element III?

The problem relies on two-pointer scanning with invariant tracking to find the pivot, swap, and reverse digits for the next greater number.

Can this algorithm handle numbers exceeding 32-bit integer limits?

Yes, the solution explicitly checks if the computed next greater integer fits in a 32-bit signed integer and returns -1 if it does not.

Why do we reverse the digits after the pivot?

Reversing ensures the suffix is in ascending order, producing the smallest possible integer greater than n while preserving the pivot swap.

How do repeated digits affect the pivot selection?

Repeated digits require scanning from the rightmost side to correctly identify the pivot and swap with the minimal larger digit, avoiding larger-than-necessary results.

Is two-pointer scanning mandatory for this problem?

While other methods exist, two-pointer scanning is optimal for minimal swaps and efficient next permutation generation, aligning with the problem's core pattern.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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 ans

Continue Practicing

#557 reverse words in a string iii #564 find the closest palindrome #567 permutation in string