Next Greater Element III

LeetCode 556 | Difficulty: Medium

Medium

Problem Description

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:

Input: n = 12
Output: 21

Example 2:

Input: n = 21
Output: -1

Constraints:

- `1 <= n <= 2^31 - 1`

Topics: Math, Two Pointers, String

---

Approach

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

---

Solutions

Solution 1: C# (Best: 35 ms)

Metric	Value
Runtime	35 ms
Memory	26.1 MB
Date	2022-01-19

Solution

public class Solution {
    public int NextGreaterElement(int n) {
        int[] arr = n.ToString().Select(x=>(int)(x-'0')).ToArray();
    int pivot = -1;
    int len = arr.Length;
    for (int i = len-1; i > 0; i--)
    {
        if (arr[i - 1] < arr[i])
        {
            pivot = i - 1;
            break;}
    }
    if(pivot == -1) return -1;
    else
    {
        int index = -1;
        for (int i = len - 1; i >= pivot; i--)
        {
            if (arr[i] > arr[pivot])
            {
                index = i;
                break;
            }
        }
        Swap(arr, pivot, index);
        Array.Reverse(arr, pivot+1, len-pivot-1);       
    }
    long result = 0;
    foreach (var item in arr)
    {
        result = 10 * result + item;
    }
    return result>Int32.MaxValue ? -1 : (int) result;

}

private void Swap(int[] arr, int i , int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.