Next Greater Element III

medium math two pointers string

Problem

Given a 32-bit integer n, return the smallest 32-bit integer > n using the same digits, or −1.

Inputn = 12443322

Output13222344

The classic 'next permutation' algorithm on digit characters.

def next_greater_element(n):
    d = list(str(n))
    i = len(d) - 2
    while i >= 0 and d[i] >= d[i + 1]: i -= 1
    if i < 0: return -1
    j = len(d) - 1
    while d[j] <= d[i]: j -= 1
    d[i], d[j] = d[j], d[i]
    d[i + 1:] = reversed(d[i + 1:])
    v = int("".join(d))
    return v if v < (1 << 31) else -1

function nextGreaterElement(n) {
  const d = String(n).split("");
  let i = d.length - 2;
  while (i >= 0 && d[i] >= d[i + 1]) i--;
  if (i < 0) return -1;
  let j = d.length - 1;
  while (d[j] <= d[i]) j--;
  [d[i], d[j]] = [d[j], d[i]];
  const tail = d.slice(i + 1).reverse();
  d.splice(i + 1, tail.length, ...tail);
  const v = Number(d.join(""));
  return v < 2147483648 ? v : -1;
}

class Solution {
    public int nextGreaterElement(int n) {
        char[] d = String.valueOf(n).toCharArray();
        int i = d.length - 2;
        while (i >= 0 && d[i] >= d[i + 1]) i--;
        if (i < 0) return -1;
        int j = d.length - 1;
        while (d[j] <= d[i]) j--;
        char t = d[i]; d[i] = d[j]; d[j] = t;
        for (int l = i + 1, r = d.length - 1; l < r; l++, r--) { t = d[l]; d[l] = d[r]; d[r] = t; }
        long v = Long.parseLong(new String(d));
        return v <= Integer.MAX_VALUE ? (int) v : -1;
    }
}

int nextGreaterElement(int n) {
    string d = to_string(n);
    int i = (int)d.size() - 2;
    while (i >= 0 && d[i] >= d[i + 1]) i--;
    if (i < 0) return -1;
    int j = d.size() - 1;
    while (d[j] <= d[i]) j--;
    swap(d[i], d[j]);
    reverse(d.begin() + i + 1, d.end());
    long long v = stoll(d);
    return v <= INT_MAX ? (int) v : -1;
}

Explanation

This is the classic next permutation trick applied to the digits of the number. We want the smallest number that is still bigger than n using the exact same digits.

Turn n into a list of digits. Scan from the right to find the first pivot: the rightmost spot i where d[i] < d[i+1]. Everything to the right of the pivot is in decreasing order (already the biggest arrangement), so the pivot is the digit we must increase. If no such pivot exists, the digits are fully descending and no larger number is possible, so we return -1.

Next, find the smallest digit to the right of the pivot that is still bigger than d[i], and swap them. After the swap, the suffix is still in decreasing order, so we reverse the suffix to make it as small as possible. A final overflow check rejects results above the 32-bit limit.

Example: n = 12443322. The pivot is the 2 (the 1-position from left where 2 < 4). We swap it with the smallest larger digit in the tail (a 3), then reverse the tail, producing 13222344.

Each step is a single linear pass over the digits, so the work is proportional to the number of digits.

Time: O(L) Space: O(L)