algoadvance

Leetcode 31. Next Permutation

Problem Statement

The problem “Next Permutation” asks you to 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). The replacement must be in place and use only constant extra memory.

Example:

  1. Input: nums = [1,2,3] Output: [1,3,2]

  2. Input: nums = [3,2,1] Output: [1,2,3]

  3. Input: nums = [1,1,5] Output: [1,5,1]

Clarifying Questions:

  1. What is the range of the input array size?
    • The array size can be from 1 to 1000.
  2. What are the possible values within the array?
    • The values are integers and can be from -1000 to 1000.
  3. Is maintaining the original array structure important?
    • Yes, the function should rearrange elements in place.

Strategy

Here is a detailed step-by-step strategy to solve the problem:

  1. Identify the rightmost ascending pair:
    • Traverse the array from the end and find the first pair where nums[i] < nums[i + 1]. Let this index be i.
  2. Find the smallest number greater than nums[i] from the right-hand side:
    • Again, traverse the array from the end and find the first index j such that nums[j] > nums[i].

  3. Swap the values at indices i and j.

  4. Reverse the sequence from index i+1 to the end of the array:
    • This ensures the sequence is the smallest possible permutation that is larger than the current one.
  5. Special Case:
    • If no such i exists (i.e., the array is in descending order), reverse the entire array to get the smallest permutation.

Code

#include <vector>
#include <algorithm>

void nextPermutation(std::vector<int>& nums) {
    int n = nums.size();
    int i = n - 2;
    
    // Step 1: Find first descending pair from the right end.
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    
    if (i >= 0) { 
        // Step 2: Find the smallest number greater than nums[i] from the right end.
        int j = n - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        // Step 3: Swap nums[i] and nums[j].
        std::swap(nums[i], nums[j]);
    }
    
    // Step 4: Reverse the part from i+1 to the end of the array.
    std::reverse(nums.begin() + i + 1, nums.end());
}

Time Complexity

Thus, the overall time complexity is O(n), which is efficient for the constraints given.

This solution uses only constant extra space, thus meeting the in-place requirement.

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