Skip to main content

40. Next Permutation

mediumAsked at Plaid

Rearrange numbers into the lexicographically next greater permutation. Plaid asks this because deterministic enumeration of equivalent reorderings is the same primitive they use when retrying batch ETL jobs in a fixed cycle.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE II OA.
  • LeetCode Discuss (2026)— Plaid permutation classic.

Problem

Implement next permutation, which rearranges nums into the lexicographically next greater permutation. If such an arrangement is not possible, it must rearrange it to 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]

Example 3

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

Approaches

1. Generate all permutations, sort, find next

Enumerate every permutation, sort, find the input's index, return the next.

Time
O(n! * n log n)
Space
O(n!)
// Don't ship. Factorial blow-up.

Tradeoff: Factorial. TLE for n > 8.

2. Standard algorithm (find pivot, swap, reverse)

1) Walk from the right; find the first index i where nums[i] < nums[i+1]. 2) Walk from the right; find the first j > i where nums[j] > nums[i]. 3) Swap nums[i] and nums[j]. 4) Reverse nums[i+1..end].

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]];
  }
  for (let lo = i + 1, hi = nums.length - 1; lo < hi; lo++, hi--) {
    [nums[lo], nums[hi]] = [nums[hi], nums[lo]];
  }
}

Tradeoff: Linear time, in-place. The 'find pivot from right' identifies the longest non-increasing suffix; swapping with the smallest-yet-larger entry guarantees the smallest possible next permutation.

Plaid-specific tips

Plaid grades this on whether you can articulate the algorithm's three steps cleanly. Bonus signal: when nums is the last permutation (strictly decreasing), the pivot search finds i = -1 and we fall through to just reversing — that's why the algorithm handles the wraparound case naturally.

Common mistakes

  • Using <= instead of < in the pivot search — misses duplicate-equal cases.
  • Looking for the smallest j greater than i instead of the rightmost — wrong answer.
  • Forgetting to reverse the suffix — leaves it in descending order, which is not the smallest next permutation.

Follow-up questions

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

  • Previous permutation — mirror algorithm.
  • kth permutation directly without enumeration (LC 60).
  • All permutations (LC 46).

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 look for the rightmost j > i with nums[j] > nums[i]?

Because the suffix is non-increasing, the rightmost such j is the smallest value still greater than nums[i]. Swapping with it gives the smallest increase at position i.

Why reverse the suffix at the end?

After the swap, the suffix is still non-increasing (you swapped with the smallest-greater). Reversing makes it ascending, which is the smallest possible arrangement of those values.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →