Explorer
Data Structures & Algorithms

Find the lexicographically next greater permutation of numbers.

Problem Statement

A permutation of an array of integers is an arrangement of its members into a sequence or linear order. The next permutation of an array of integers is the next lexicographically greater permutation of its integer. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order). Return the modified array in-place.

Examples

Input: nums = [1, 2, 3]

Output: [1, 3, 2]

Explanation: [1, 3, 2] is the next lexicographically greater permutation.

Input: nums = [3, 2, 1]

Output: [1, 2, 3]

Explanation: [1, 2, 3] is the next lexicographically greater permutation.

Complexity

Time Complexity: O(N)

Space Complexity: O(1)

Hints

šŸ’” Hint 1: Find the first index i from the right where nums[i] < nums[i + 1]. šŸ’” Hint 2: If such an index exists, find the smallest element to the right of i that is strictly greater than nums[i], and swap them. šŸ’” Hint 3: Finally, reverse everything to the right of index i to get the lexicographically next permutation.

Editorial & Approach

Problem Overview & Intuition

To find the next lexicographical permutation, we find the longest non-increasing suffix. The element preceding this suffix is swapped with the smallest element in the suffix that is greater than it, and the suffix is reversed into ascending order.

Step-by-Step Approach

  1. Find the pivot index i from the right such that nums[i] < nums[i + 1].
  2. If no such index exists (entire array is descending), reverse the whole array.
  3. Otherwise, find index j > i from the right where nums[j] > nums[i].
  4. Swap nums[i] and nums[j].
  5. Reverse the subarray from i + 1 to the end.
  6. Return nums.

Optimal Implementation (JavaScript)

function nextPermutation(nums) {
  let i = nums.length - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) i--;
  if (i >= 0) {
    let j = nums.length - 1;
    while (nums[j] <= nums[i]) j--;
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }
  let left = i + 1, right = nums.length - 1;
  while (left < right) {
    [nums[left], nums[right]] = [nums[right], nums[left]];
    left++;
    right--;
  }
  return nums;
}

Complexity Analysis

Time Complexity O(N) ā€” at most two scans and one reversal pass.
Space Complexity O(1) ā€” in-place manipulation.

Edge Cases & Corner Traps Handled

  • Array sorted in descending order: wraps around to ascending order.
  • Array with duplicate values.
  • Single element array.

Next Permutation

Medium
A permutation of an array of integers is an arrangement of its members into a sequence or linear order. The next permutation of an array of integers is the next lexicographically greater permutation of its integer. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order). Return the modified array in-place.
Example Scenarios
1Example 1
Input: nums = [1, 2, 3]
Output: [1, 3, 2]
Explanation:

[1, 3, 2] is the next lexicographically greater permutation.

2Example 2
Input: nums = [3, 2, 1]
Output: [1, 2, 3]
Explanation:

[1, 2, 3] is the next lexicographically greater permutation.

Editor
Loading Editor...
nums =
[1, 2, 3]
Output:Click "Run" above to execute and verify your code here.
[1,3,2]