Next Permutation

The problem

Given an array of integers, rearrange it to its next lexicographically greater permutation. If no greater permutation exists, return the smallest permutation.

To make the number minimally larger, the modification must happen as far to the right as possible. The first position from the right that can increase is the first dip where arr[i] < arr[i + 1]; swapping it with the smallest strictly larger value to its right, then reversing the remaining suffix into ascending order, ensures the smallest step up.

Full solution

Pivot swap and suffix reversal: find the rightmost dip, swap it with the smallest strictly larger value to its right, then reverse the descending tail. One pass in place, O(n) time and O(1) space; a fully descending input has no pivot and reverses to the smallest permutation.

def next_permutation(arr: list[int]) -> list[int]:
    n = len(arr)
    # pivot: first index from the right where the sequence stops descending
    i = n - 2
    while i >= 0 and arr[i] >= arr[i + 1]:
        i -= 1
    if i >= 0:
        # smallest value strictly greater than the pivot lives in the descending suffix
        j = n - 1
        while arr[j] <= arr[i]:
            j -= 1
        arr[i], arr[j] = arr[j], arr[i]
    # the suffix is descending; reversing makes it the smallest possible tail
    arr[i + 1:] = arr[i + 1:][::-1]
    return arr

function nextPermutation(arr) {
  const n = arr.length;
  let i = n - 2;
  while (i >= 0 && arr[i] >= arr[i + 1]) i--;
  if (i >= 0) {
    let j = n - 1;
    while (arr[j] <= arr[i]) j--;
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  for (let lo = i + 1, hi = n - 1; lo < hi; lo++, hi--) {
    [arr[lo], arr[hi]] = [arr[hi], arr[lo]];
  }
  return arr;
}

The theory behind it

Arrays — the ground this problem stands on. All Arrays problems

What Arrays is

An array is a row of fixed boxes laid side by side in computer memory, like numbered lockers in a hallway. Because each box occupies identical space and sits directly next to its neighbors, jumping to locker zero or locker ten thousand takes the exact same tiny fraction of time. Every box holds an item of the same type, addressed by an offset number called an index.

When to reach for it

Reach for an array when items arrive in a known sequence and need immediate retrieval by position number. Problems asking for running totals, prefix accumulations, cyclic rotations, or in-place rearrangements signal array mechanics. Whenever constraints require constant-time random lookups or contiguous cache scans across fixed collections, a flat sequence is the default container.

How the pattern works

Visualize a tape with zero-indexed slots stretching from start to end. Keep track of write and read cursors when modifying contents without allocating helper buffers. For running computations, maintain an invariant such as having processed all elements left of the current index while pending elements wait to the right. When modifying entries in place, consider scanning backwards from the end so unread data is not overwritten.

What each operation costs

Which roles need this problem

Arrays is a core topic for these 25 roles — if you're targeting one of them, this problem is early in your path, not optional.

Secondary for 3 more roles, including Database Engineer, Bioinformatics Engineer, Networking Engineer.