DSA SheetMedium
EditorialPractice

2 POINTERS › TWO POINTER ON ARRAYS

Next Greater Element III

MediumEditorial · 7 minGenerated by gpt-5.6-luna · Aug 25

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionwhy the smallest larger number is a local change followed by the smallest suffix

Numbers with the same digits are ordered exactly like their digit strings when all strings have the same length. So the problem asks for the next lexicographically greater permutation. To stay as small as possible, you must preserve the longest prefix you can and change a digit as far to the right as possible.

Scan from right to left until you find the first position i where s[i] < s[i + 1]. Everything after i is non-increasing, so that suffix is already the largest arrangement of its digits. Swap s[i] with the smallest digit in the suffix that is larger than it, then reverse the suffix. The swap makes the number larger, and the reversal makes the remaining digits as small as possible.

A digit string with a pivot and a non-increasing suffixThe figure shows a row of digit cells. A fixed prefix sits on the left, followed by a marked pivot cell whose digit is smaller than the digit immediately to its right. The cells after the pivot form a non-increasing suffix. One suffix cell containing the smallest digit larger than the pivot is marked as the replacement. After the swap, the suffix cells are reversed into increasing order. The picture highlights that the pivot is the rightmost position that can be increased, while the suffix is minimized afterward.1237654212423567pivot becomes 4reverse suffixdigit prefixunchangedpivot: 3non-increasing suffix7 ≥ 6 ≥ 5 ≥ 4 ≥ 2smallest suffix digit > pivot: 4smallest larger digit stringreversed suffix → increasingOnly the rightmost ascent can increase the longest unchanged prefix.

Approach

  1. Convert n to a string so each digit can be compared and rearranged directly; arithmetic digit extraction would make the permutation logic harder to express and would discard leading-position information.
  2. Set i to the second-to-last index and move it left while s[i] >= s[i + 1]; this skips the suffix that is already in non-increasing order, and if no index remains, the entire number is the largest permutation.
  3. Set j to the last index and move it left while s[j] <= s[i]; the suffix is non-increasing, so the first digit found this way is the smallest digit strictly larger than the pivot.
  4. Swap s[i] and s[j] to create the smallest possible increase at the rightmost changeable position; choosing an earlier position would make the result unnecessarily larger.
  5. Reverse the range after i because the suffix was non-increasing before the swap and must become increasing after the smallest valid pivot replacement; leaving it descending would produce a larger valid permutation.
  6. Convert the rearranged string to a 64-bit integer before returning it; this prevents an intermediate overflow, and comparing with INT_MAX enforces the required 32-bit result limit.

Complexitythe input has at most ten digits, but the permutation argument is general

MEASUREBOUNDWHY
TimeO(d)The pivot scan, replacement scan, suffix reversal, and conversion each inspect at most d digits. In the worst case, the scans and reversal touch the whole digit string, and no digit is processed more than a constant number of times.
SpaceO(d) extraThe digit string needs O(d) working storage; the returned integer is required output and is excluded. Under the given constraint d is at most 10, so the working space is bounded by a constant in this problem, even though the general digit-based bound is O(d).
Here d is the number of decimal digits in n.

Annotated solutionC++ · next-permutation structure · complete judge-ready implementation

CPPFind the pivot, exchange it with the smallest larger suffix digit, reverse the suffix, and check the 32-bit limit.
#include <algorithm>
#include <climits>
#include <string>

using namespace std;

class Solution {
public:
    int nextGreaterElement(int n) {
        string s = to_string(n);
        int len = static_cast<int>(s.size());
        int i = len - 2;

        while (i >= 0 && s[i] >= s[i + 1]) {
            --i;
        }

        if (i < 0) {
            return -1;
        }

        int j = len - 1;
        while (s[j] <= s[i]) {
            --j;
        }

        swap(s[i], s[j]);
        reverse(s.begin() + i + 1, s.end());

        long long result = stoll(s);
        return result > INT_MAX ? -1 : static_cast<int>(result);
    }
};

The two scans rely on the suffix being non-increasing. Because i is the first valid position found while moving from the right, every position after i belongs to that suffix. Its digits are already arranged from large to small, so after swapping in the smallest larger digit, reversing the suffix is enough to obtain increasing order without another search or sort.

Common mistakestwo wrong shapes that often look plausible

Previous · Next Permutation