Skip to main content

40. Next Permutation

mediumAsked at Ola

Rearrange numbers into the next lexicographically greater permutation.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array of integers nums, find the next permutation. If such an arrangement is not possible, it must rearrange it to the lowest possible order (sorted ascending). Must be done in-place.

Constraints

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

Examples

Example 1

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

Example 2

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

Approaches

1. Enumerate permutations

Generate all permutations, sort, find current, return the next.

Time
O(n! * n)
Space
O(n!)
// brute permutation; intractable beyond n=8

Tradeoff:

2. Pivot and reverse

Find the rightmost i with nums[i] < nums[i+1]; swap nums[i] with the smallest larger value to its right; reverse the suffix.

Time
O(n)
Space
O(1)
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 l = i + 1, r = nums.length - 1;
  while (l < r) { [nums[l], nums[r]] = [nums[r], nums[l]]; l++; r--; }
}

Tradeoff:

Ola-specific tips

Ola tests this for in-place index manipulation; tie it to producing the next deterministic dispatch order under a stable tiebreak.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Next Permutation and other Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →