Next Permutation — C++ Coding Problem
Difficulty: medium | Category: array
Problem Description
A permutation of an array of integers is an arrangement of its members into a sequence or linear order. Given an array of integers `nums`, find the **next permutation** (lexicographically next greater arrangement). If no such arrangement is possible, rearrange it to the lowest possible order (ascending). **Algorithm:** 1. Find largest index `i` where `nums[i] < nums[i+1]`. 2. Find largest index `j > i` where `nums[j] > nums[i]`. 3. Swap `nums[i]` and `nums[j]`. 4. Reverse the suffix starting at `nums[i+1]`. The replacement must be **in place** with only constant extra memory.
Examples
Example 1
Input: nums = [1,2,3]
Output: [1,3,2]
Example 2
Input: nums = [3,2,1]
Output: [1,2,3]
Example 3
Input: nums = [1,1,5]
Output: [1,5,1]