thesarfo

Reference

Next Permutation

Finding the next lexicographically larger arrangement of an array's elements using the breakpoint + swap + reverse technique.

views 0

The next lexicographically larger arrangement of an array’s elements; if none exists, wrap around to the smallest (fully sorted ascending). [3,1,2] → next is [3,2,1]; [3,2,1] → wraps to [1,2,3].

Brute force: generate every permutation, sort them, find the current one, return the next — O(n! × n), infeasible for large arrays.

Optimal — “longer prefix match”: for [2,1,5,4,3,0,0]:

  1. Find the breakpoint: the first index i from the right where arr[i] < arr[i+1] (index 1, since 1 < 5).
  2. Find the smallest value to the right of the breakpoint that’s still greater than arr[i] (that’s 3, at index 4).
  3. Swap those two: [2,3,5,4,1,0,0].
  4. Reverse everything after the breakpoint index to get the smallest possible ordering of the remainder: reversing [5,4,1,0,0] gives [0,0,1,4,5].

Final result: [2,3,0,0,1,4,5].