Next Permutation medium

Problem Statement

Given an array of integers nums, find the next permutation of the array in lexicographical order. If no next permutation exists, then the array should be mutated to the first permutation (least lexicographical order).

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]

Steps and Explanation

The algorithm to find the next permutation involves these steps:

1. Find the first decreasing digit from the right: Starting from the rightmost digit, we scan the array to find the first digit that is smaller than its right neighbor. Let's call this index i. If no such digit is found (the array is in descending order), this means it's the last permutation, and we need to reverse the entire array to get the first permutation.

2. Find the smallest digit greater than the digit at index i: We search for the smallest digit in the subarray to the right of i that is greater than the digit at index i. Let's call this digit j.

3. Swap i and j: We swap the digits at indices i and j.

4. Reverse the subarray to the right of i: We reverse the subarray from index i + 1 to the end of the array. This ensures that the subarray to the right of i is in ascending order, resulting in the lexicographically next permutation.

Code (C#)

using System;

public class Solution {
    public void NextPermutation(int[] nums) {
        int i = nums.Length - 2;

        // 1. Find the first decreasing digit from the right
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        if (i >= 0) {
            int j = nums.Length - 1;

            // 2. Find the smallest digit greater than nums[i]
            while (j > i && nums[j] <= nums[i]) {
                j--;
            }

            // 3. Swap nums[i] and nums[j]
            Swap(nums, i, j);
        }

        // 4. Reverse the subarray to the right of i
        Reverse(nums, i + 1, nums.Length - 1);
    }

    private void Swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void Reverse(int[] nums, int start, int end) {
        while (start < end) {
            Swap(nums, start, end);
            start++;
            end--;
        }
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the array. We iterate through the array at most three times (finding the decreasing digit, finding the smallest greater digit, and reversing the subarray).
• Space Complexity: O(1). The algorithm operates in place and uses only constant extra space.