algoadvance

Leetcode 31. Next Permutation

Problem Statement

The problem “Next Permutation” can be described as follows:

Implement a function that rearranges numbers into the lexicographically next greater permutation of numbers. If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

For example:

• The next permutation of [1,2,3] is [1,3,2].
• The next permutation of [3,2,1] is [1,2,3].
• The next permutation of [1,1,5] is [1,5,1].

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

Clarifying Questions

1. Input constraints: What is the range of numbers and size of the array?
   • Answer: The input array will contain integers within the range [-10^6, 10^6], and its length n will be between 1 and 1000.
2. Handling edge cases: What should be done if the array is empty or contains only one element?
   • Answer: If the array contains zero or one element, it can be considered as already being the smallest permutation.

Strategy

To solve this problem, we can use the following steps:

1. Find the longest non-increasing suffix: Start from the end of the array and find the first element that is smaller than its next element. This element is called the pivot.
2. Find the rightmost successor to the pivot in the suffix: From the end of the array, find the smallest element that is larger than the pivot.
3. Swap the pivot and the successor: Swap these two elements.
4. Reverse the suffix: Reverse the order of the elements in the suffix.

Code

Here is the implementation of the above steps in Java:

class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) return;
        
        int i = nums.length - 2;
        
        // Step 1: Find the longest non-increasing suffix
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        
        // If the entire array is non-increasing, reverse the whole array
        if (i >= 0) {
            // Step 2: Find rightmost element that exceeds nums[i]
            int j = nums.length - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            // Step 3: Swap the pivot with nums[j]
            swap(nums, i, j);
        }
        
        // Step 4: Reverse the suffix
        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--);
        }
    }
}

Time Complexity

• Time Complexity: The time complexity is O(n), where n is the length of the array. This results from scanning the array backwards, swapping elements, and then reversing part of the array.

• Space Complexity: The space complexity is O(1) because we are modifying the array in place without using extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?