Skip to main content

40. Next Permutation

mediumAsked at Vercel

Rearrange numbers into the lexicographically next greater permutation in-place. Vercel asks this for the find-pivot-then-swap-then-reverse algorithm — a classic that distinguishes candidates who have actually studied the canonical patterns.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2026-Q1)— Vercel platform onsite; in-place version expected.
  • Blind (2025-Q4)— Listed in Vercel platform engineer screen.

Problem

Implement next permutation, which 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.

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]

Explanation: Already the largest; wraps to smallest.

Example 3

Input
nums = [1,1,5]
Output
[1,5,1]

Approaches

1. Generate all permutations and find the next

Enumerate all permutations sorted lexicographically; return the one after nums.

Time
O(n! * n)
Space
O(n!)
// Don't actually do this; included for contrast.
// Factorial blow-up makes it infeasible even at n=15.

Tradeoff: Factorial. Mention only to set the bar.

2. Find pivot, swap, reverse suffix (optimal)

From right, find first i where nums[i] < nums[i+1]. From right, find first j > i where nums[j] > nums[i]. Swap nums[i] and nums[j]. Reverse nums[i+1..end].

Time
O(n)
Space
O(1)
function nextPermutation(nums) {
  const n = nums.length;
  let i = n - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) i--;
  if (i >= 0) {
    let j = n - 1;
    while (nums[j] <= nums[i]) j--;
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }
  // Reverse suffix from i+1
  let l = i + 1, r = n - 1;
  while (l < r) { [nums[l], nums[r]] = [nums[r], nums[l]]; l++; r--; }
}

Tradeoff: O(n) single algorithm with three sweeps. The 'pivot' is the first decreasing-from-right index; the suffix after it is sorted descending, so reversing makes it ascending.

Vercel-specific tips

Vercel grades for the canonical three-step algorithm. Bonus signal: explaining WHY the suffix after the pivot is sorted descending (because the while loop stops at the first non-decreasing element) and why reversing it gives the smallest valid arrangement.

Common mistakes

  • Sorting the suffix instead of reversing it — O(n log n) for no reason; reversal suffices because it's already descending.
  • Off-by-one on the pivot find — must check nums[i] < nums[i+1] strictly.
  • Forgetting the 'no pivot found' case (descending input) — must reverse the whole array.

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Previous Permutation — symmetric.
  • k-th Permutation (LC 60) — direct factorial-based construction.
  • Permutations (LC 46) — generate all.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the suffix descending?

We stopped at the first i where nums[i] < nums[i+1]. Therefore, for every k > i, nums[k] >= nums[k+1] — the suffix is descending. After swapping pivot with the just-bigger-than-pivot element, it remains descending; reversing makes it ascending = smallest.

Why pick the just-greater-than-pivot from the right?

We want the smallest valid bump. Picking from the right gives the smallest element strictly greater than the pivot, which is exactly what 'next permutation' needs.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →