Given an array arr[] of n integers, rearrange the numbers in place into the…

Concept. All the arrangements of one fixed multiset of numbers can be listed in lexicographic (dictionary) order, and the next permutation of an arrangement is its immediate successor in that list. Two facts govern that successor. First, a block of numbers that reads non-increasing from left to right is already the largest arrangement of its own elements, so it can never be increased without touching something to its left. Second, the successor must change the array as far to the right as possible and by as little as possible. Together these force the change to happen at the last index i where arr[i] < arr[i+1] — the pivot — and they force everything to the right of the pivot to become as small as possible afterwards. When no such index exists the whole array is non-increasing, it is the maximum arrangement, and its successor wraps around to the minimum, which is the array in ascending order.

Application. The concept turns directly into five steps, of which only the two scans and the reversal actually traverse the array:

1. Scan from the right and find the largest index i with arr[i] < arr[i+1]. Everything after i is non-increasing, hence already maximal, so i is the rightmost position at which the array can be increased at all.

2. If no such i exists, the entire array is non-increasing and therefore the largest arrangement. Reverse the whole array to obtain the smallest arrangement and stop.

3. Otherwise scan from the right again and find the largest index j > i with arr[j] > arr[i]. Because the suffix is non-increasing, this rightmost qualifying element is the smallest value in the suffix that still exceeds arr[i], so putting it at the pivot is the smallest legal increase there.

4. Swap arr[i] and arr[j]. Write v for the pivot value that sat at index i; after the swap v sits at index j. The suffix is still non-increasing there, because every suffix element before index j is at least as large as the value that was at index j and therefore greater than v, while every element after index j is at most v — index j was chosen as the rightmost position holding a value greater than v.

5. Reverse the segment arr[i+1..n-1]. A non-increasing block reversed becomes non-decreasing, which is the smallest arrangement of those elements, so the array as a whole is now the immediate successor.

Cross-check. Tracing the first worked example, arr[] = [2, 4, 1, 7, 5, 0]:

The trace lands on 2 4 5 0 1 7, which is the stated output. The other two examples check the two remaining shapes:

• For [3, 2, 1] every adjacent pair decreases, so no pivot exists and step 2 reverses the whole array to 1 2 3 — the wrap-around case.

• For [3, 4, 2, 5, 1] the pivot is i = 2, value 2, the rightmost larger element is 5 at j = 3, the swap gives 3, 4, 5, 2, 1, and reversing the suffix 2, 1 gives 3 4 5 1 2.

Why the result is exactly the successor. The prefix before the pivot is untouched, so no arrangement that differs earlier can sit between the input and the output. At the pivot the value strictly increases, so the output is greater than the input, and it increases by the least amount available, so no smaller increase at that position exists. After the pivot the elements are placed in ascending order, the smallest arrangement of what is left. Hence nothing lies strictly between the two arrangements.

Complexity and pitfalls.

• The two scans and the suffix reversal are each a single linear pass and the swap is constant time, so the running time is O(n) and the extra space is O(1). Sorting would cost O(n log n) and enumerating permutations would be factorial, both far too slow at the constraint bound.

• The pivot test must be strict: arr[i] < arr[i+1]. Using arr[i] <= arr[i+1] on an input such as [3, 1, 1] reports a pivot at i = 1 and then finds no element greater than 1 to swap with.

• Take the rightmost j with arr[j] > arr[i], not the first larger element seen from the left. On [1, 5, 3, 3, 2] the leftmost choice swaps in 5 and produces an arrangement far beyond the immediate successor; the correct answer is 2 1 3 3 5.

• The suffix must be reversed, not left as it is. Immediately after the swap the suffix is still non-increasing, i.e. maximal, so stopping there yields an arrangement much larger than the true successor. Reversing is enough — sorting the suffix would give the same order at a higher cost.

• Duplicate values need no special handling: the strict pivot test and the rightmost-successor rule already produce the correct arrangement, and a single-element array simply reverses to itself.