Problem Statement

Given an array of integers nums, return the next permutation of nums.

A permutation of the array is an arrangement of its elements in the linear order or particular sequence.

• For example, permutations of the [2, 1, 3] array are [3,2,1], [3,1,2], [1,2,3], [1,3,2], [2, 1, 3], and [2, 3, 1].

A next permutation of the array is the next smallest lexicographically greater permutation of array elements.

• For example, next permutation of [2, 1, 3] is [2, 3, 1], which is smallest lexicographically greater permutation.

If no higher permutation is possible, the array should be rearranged into its lowest possible order (ascending).

• For example, next permutation for [3, 2, 1] is [1, 2, 3] as [3, 2, 1] doesn't have lexicographically larger permutation.

Examples

• Example 1:

  • Input: [1, 3, 5, 4, 2]
  • Expected Output: [1, 4, 2, 3, 5]
  • Justification: The next permutation is obtained by swapping 3 with the next higher number (4) and then sorting the numbers after 4 in ascending order.

• Example 2:

  • Input: [2, 3, 6, 5, 4, 1]
  • Expected Output: [2, 4, 1, 3, 5, 6]
  • Justification: The next permutation is found by swapping 3 with the next higher number (4) in the sequence following it and then sorting the numbers after 4 in ascending order.

• Example 3:

  • Input: [1, 1, 5]
  • Expected Output: [1, 5, 1]
  • Justification: The next immediate permutation after [1, 1, 5] is [1, 5, 1].

Try it yourself

Try solving this question here: