SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

Given an array of integers nums, find the next permutation of the array in lexicographically increasing order. If such an arrangement is not possible (i.e., the array is sorted in descending order), rearrange it to the lowest possible order (i.e., sorted in ascending order). The replacement must be done in-place with only constant extra memory.

Intuition

The next permutation problem is about finding the smallest lexicographical order that is greater than the current sequence. To do this, we need to modify the sequence in a way that alters the order minimally while still making it larger. If the sequence is entirely non-increasing, it means we're at the largest permutation, and the next permutation should reset it to the smallest permutation (which is the reverse of the current sequence).

Approach

1. Identify the rightmost ascent: Start from the end of the array and find the first element that is smaller than its next element (nums[k] < nums[k + 1]). This is the element that needs to be swapped to make a bigger permutation.

2. Find the element to swap with: Once we have k, find the largest element to the right of k that is larger than nums[k]. This ensures that the next permutation is the smallest possible increase.

3. Swap the elements: Swap nums[k] with the identified element.

4. Reverse the subarray: Finally, reverse the portion of the array that comes after k to get the smallest possible order for that subarray, completing the next permutation.

Complexity

Time Complexity:

O(n), where n is the number of elements in the array. We traverse the array a few times to find the necessary elements and reverse part of the array.

Space Complexity:

O(1), since the algorithm only modifies the input array in place without using additional space.

Code

C++

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int k = nums.size() - 2;
        while (k >= 0 && nums[k] >= nums[k + 1]) {
            k--;
        }
        if (k == -1) {
            reverse(nums.begin(), nums.end());
            return;
        }
        int l = nums.size() - 1;
        while (nums[l] <= nums[k]) {
            l--;
        }
        swap(nums[k], nums[l]);
        reverse(nums.begin() + k + 1, nums.end());
    }
};

Python

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        k = len(nums) - 2
        while k >= 0 and nums[k] >= nums[k + 1]:
            k -= 1
        if k == -1:
            nums.reverse()
            return
        l = len(nums) - 1
        while nums[l] <= nums[k]:
            l -= 1
        nums[k], nums[l] = nums[l], nums[k]
        left, right = k + 1, len(nums) - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

Java

class Solution {
    public void nextPermutation(int[] nums) {
        int k = nums.length - 2;
        while (k >= 0 && nums[k] >= nums[k + 1]) {
            k--;
        }
        if (k == -1) {
            reverse(nums, 0, nums.length - 1);
            return;
        }
        int l = nums.length - 1;
        while (nums[l] <= nums[k]) {
            l--;
        }
        swap(nums, k, l);
        reverse(nums, k + 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--;
        }
    }
}

JavaScript

function nextPermutation(n){
    let k=n.length-2;
    while(k>=0 && n[k]>=n[k+1]){
        k--;
    }
    if(k === -1){
        n.reverse();
        return;
    }
    let l=n.length-1;
    while(n[l] <=n[k]){
        l--;
    }
    [n[k], n[l]] =[n[l], n[k]];
    let left=k+1;
    let right=n.length-1;
    while(left < right){

        [n[left], n[right]]=[n[right], n[left]];
        left++;
        right--;
    }
}