15. Next Permutation

Given an array representing a permutation, rearrange it into the next lexicographically greater permutation. If no greater permutation exists, rearrange it into the lowest possible order (sorted ascending). Print the result.

Input: The first line contains an integer n. The second line contains n space-separated integers forming a permutation. Output: Print the next lexicographically greater permutation, space-separated on one line.

1 <= n <= 10^5

The wrap-around case (already the largest permutation, reverse to get the smallest) is a real edge case worth testing explicitly - it's easy to forget when focused on the main pivot-and-swap logic.

Given an arrangement of numbers, find the very NEXT arrangement that would come after it if you listed every possible arrangement in increasing order - and if this is already the very last one, wrap back around to the smallest arrangement. Brute force: Generate every possible permutation of the array, sort them all, and find the one immediately after the current arrangement - this is astronomically slow (factorial time) and completely impractical beyond tiny arrays. Optimised: The 'next permutation' can always be found by identifying the RIGHTMOST place where increasing order breaks down (the pivot), making the SMALLEST possible increase there (swapping in the smallest larger value from the tail), then arranging everything after that point into its smallest possible order (reversing, since the tail was in decreasing order before the swap) - this direct construction avoids generating all permutations entirely.

Rather than generating every permutation, find the rightmost position i where arr[i] < arr[i+1] (the 'pivot' - the suffix starting at i+1 is already the highest possible arrangement for those elements, so we must change something at or before i). Then scan the suffix after i to find the smallest value greater than arr[i], swap it into position i, and re-sort the suffix after i in ascending order (an O(n log n) sort) to get the smallest possible arrangement for the remaining positions. This avoids ever enumerating other permutations, going straight to the next one, though the extra sort step does more work than is strictly necessary. Time: O(n log n) Space: O(n)

Do the same pivot-finding and swap as above, but observe that the suffix after the pivot is always in strictly non-increasing order before the swap (that's precisely why the pivot was the rightmost ascent). After swapping in the smallest larger element, that suffix is still non-increasing, so instead of sorting it, simply reverse it in place to turn it into ascending order - achieving the same result as sorting but in linear time and with no extra memory. If no pivot exists at all (the whole array is non-increasing), reversing the entire array directly produces the required lowest-order permutation. Time: O(n) Space: O(1)

Generate every permutation of the array (for example via recursive backtracking that swaps elements into each position), collect them all, and sort the resulting list lexicographically. Find the current permutation's position in that sorted list and return the one immediately after it (wrapping to the smallest if the current one is last). This is guaranteed correct by brute enumeration, but generating and sorting all n! permutations is astronomically slow for anything beyond tiny n. Time: O(n! * n) Space: O(n! * n)

1. Scan from the right end looking for the first position where a number is SMALLER than the number right after it (this is the 'pivot'). 2. If no such position exists, the whole array is already the largest possible arrangement - reverse it entirely to get back to the smallest. 3. Otherwise, scan from the right again to find the smallest number that's still LARGER than the pivot, and swap it with the pivot. 4. Reverse everything after the pivot's original position - this puts the 'tail' back into its smallest possible order, giving the smallest possible increase overall.

Time: O(n) - each of the three steps (find pivot, find swap candidate, reverse the tail) is a single linear scan. Space: O(1) - the rearrangement happens directly within the original array.

n = 1 (only one permutation exists, output unchanged); the array already at its highest permutation, i.e. fully descending (must wrap to the fully ascending order); and n = 10^5 (largest, confirming the pivot-and-reverse approach is O(n)).

Be ready to explain WHY the segment after the pivot is always in strictly decreasing order before your swap (this is a direct consequence of how the pivot was defined) - this is exactly why reversing it (rather than re-sorting it) correctly and efficiently produces the smallest possible tail arrangement.