LeetCode //C - 31. Next Permutation

31. Next Permutation

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

• For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

• For example, the next permutation of arr = [1,2,3] is [1,3,2].
• Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
• While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.
 

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]

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

From: LeetCode
Link: 31. Next Permutation

---

Solution:

Ideas:

1. Find the first decreasing element from the right: Traverse the array from the right end. Find the first element nums[i] such that nums[i] < nums[i + 1]. If no such element exists, the entire array is in descending order, and this is the last permutation. We need to reverse the array to get the first permutation (lowest possible order).

2. Find the element greater than the first decreasing element: If such an element (nums[i]) is found in step 1, then find the smallest element on the right side of i (let’s say nums[j]) that is greater than nums[i].

3. Swap nums[i] and nums[j]: Swap these two elements to increase the permutation by the smallest possible amount.

4. Reverse the subarray to the right of i: Finally, reverse the subarray that lies to the right of i to get the lowest possible (ascending) order for this subarray, ensuring the next lexicographical permutation.

Code:

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void reverse(int* nums, int start, int end) {
    while (start < end) {
        swap(&nums[start], &nums[end]);
        start++;
        end--;
    }
}

void nextPermutation(int* nums, int numsSize) {
    int i = numsSize - 2;

    // Find the first element from the right that is smaller than the element to its right
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }

    if (i >= 0) {
        int j = numsSize - 1;
        // Find the element larger than nums[i] to swap with
        while (nums[j] <= nums[i]) {
            j--;
        }
        swap(&nums[i], &nums[j]);
    }

    // Reverse the numbers after the position i
    reverse(nums, i + 1, numsSize - 1);
}