Next Permutation

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

Try this Problem on your own or check similar problems:

Solution:

Java
JavaScript
Python
C++

class Solution {
  public void nextPermutation(int[] nums) {
      int startOfFirstIncreasingSeq = -1;
      for(int i = nums.length - 1; i > 0; --i){
          if(nums[i] > nums[i - 1]) {
              startOfFirstIncreasingSeq = i - 1;
              break;
          }
      }

      if(startOfFirstIncreasingSeq == -1){
          reverse(nums, 0);
          return;
      }

      int minimumElementLargerThanStartOfSeq = Integer.MAX_VALUE, idx = -1;
      for(int i = nums.length - 1; i > startOfFirstIncreasingSeq; --i){
          if(nums[i] > nums[startOfFirstIncreasingSeq] && nums[i] < minimumElementLargerThanStartOfSeq){
              minimumElementLargerThanStartOfSeq = nums[i];
              idx = i;
          }
      }

      swap(nums, idx, startOfFirstIncreasingSeq);
      reverse(nums, startOfFirstIncreasingSeq + 1);
  }

  private void reverse(int[] nums, int start){
      int n = nums.length, i =  start, j = n - 1;
      while(i < j){
          swap(nums, i++, j--);
      }
  }

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

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function (nums) {
  let startOfFirstIncreasingSeq = -1;
  for (let i = nums.length - 1; i > 0; i--) {
    if (nums[i] > nums[i - 1]) {
      startOfFirstIncreasingSeq = i - 1;
      break;
    }
  }

  if (startOfFirstIncreasingSeq === -1) {
    reverse(nums, 0);
    return;
  }

  let minimumElementLargerThanStartOfSeq = Infinity;
  let idx = -1;
  for (let i = nums.length - 1; i > startOfFirstIncreasingSeq; i--) {
    if (
      nums[i] > nums[startOfFirstIncreasingSeq] &&
      nums[i] < minimumElementLargerThanStartOfSeq
    ) {
      minimumElementLargerThanStartOfSeq = nums[i];
      idx = i;
    }
  }

  swap(nums, idx, startOfFirstIncreasingSeq);
  reverse(nums, startOfFirstIncreasingSeq + 1);
};

function reverse(nums, start) {
  let i = start;
  let j = nums.length - 1;
  while (i < j) {
    swap(nums, i++, j--);
  }
}

function swap(nums, i, j) {
  let temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        start_of_first_increasing_seq = -1
        for i in range(len(nums) - 1, 0, -1):
            if nums[i] > nums[i - 1]:
                start_of_first_increasing_seq = i - 1
                break

        if start_of_first_increasing_seq == -1:
            nums.reverse()
            return

        minimum_element_larger_than_start_of_seq = float('inf')
        idx = -1
        for i in range(len(nums) - 1, start_of_first_increasing_seq, -1):
            if nums[i] > nums[start_of_first_increasing_seq] and nums[i] < minimum_element_larger_than_start_of_seq:
                minimum_element_larger_than_start_of_seq = nums[i]
                idx = i

        nums[idx], nums[start_of_first_increasing_seq] = nums[start_of_first_increasing_seq], nums[idx]
        nums[start_of_first_increasing_seq + 1:] = reversed(nums[start_of_first_increasing_seq + 1:])

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int startOfFirstIncreasingSeq = -1;
        for (int i = nums.size() - 1; i > 0; --i) {
            if (nums[i] > nums[i - 1]) {
                startOfFirstIncreasingSeq = i - 1;
                break;
            }
        }

        if (startOfFirstIncreasingSeq == -1) {
            reverse(nums.begin(), nums.end());
            return;
        }

        int minimumElementLargerThanStartOfSeq = INT_MAX;
        int idx = -1;
        for (int i = nums.size() - 1; i > startOfFirstIncreasingSeq; --i) {
            if (nums[i] > nums[startOfFirstIncreasingSeq] && nums[i] < minimumElementLargerThanStartOfSeq) {
                minimumElementLargerThanStartOfSeq = nums[i];
                idx = i;
            }
        }

        swap(nums[idx], nums[startOfFirstIncreasingSeq]);
        reverse(nums.begin() + startOfFirstIncreasingSeq + 1, nums.end());
    }
};

Time/Space Complexity:

Time Complexity: O(n)
Space Complexity: O(1)

Explanation:

We only iterate through the array leading to linear time complexity and since we're doing only in place operations, we have constant space complexity. The trick to the question is to find the first increasing subsequence (iterating from the end of array), since in the case the whole array is decreasing the next permutation would be its reverse order (e.g. 3,2,1 to 1,2,3). When we find our increasing subsequence, we know that if we find the next larger number (minimum number in the rest of array that's larger than our sequence start) we can replace our sequence start element with it and sort the rest of array giving us the next iteration. But note that we don't really need to sort, since we know that numbers in the rest of array that aren't part of the increasing sequence, form a decreasing sequence so it's enough to reverse them to get increasing sorted sequence.

Example 1:​

Example 2:​

Example 3:​

Constraints:​

Solution:​

Time/Space Complexity:​

Explanation:​