Skip to main content

40. Next Permutation

mediumAsked at Snowflake

Rearrange numbers to the lexicographically next greater permutation in place. Snowflake asks this to test whether you can articulate the three-step swap-and-reverse algorithm — a precise, in-place transformation similar to executor-side row reorderings.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake execution-engine team uses this in onsites.
  • LeetCode Discuss (2025-10)— Reported at Snowflake SDE-I screens.

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]

Example 3

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

Approaches

1. Enumerate all permutations, sort, find next

Generate every permutation, sort lexicographically, find current, return next.

Time
O(n! * n)
Space
O(n! * n)
// Permute exponentially, find current, take next. Don't ship.
// Just acknowledge as the brute force.

Tradeoff: Factorial. Mention only to reject.

2. Pivot + swap + reverse (optimal)

1) Find the largest i such that nums[i] < nums[i+1]. 2) Find the largest j > i such that nums[j] > nums[i]. 3) Swap i and j. 4) Reverse the suffix after i.

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]];
  }
  // Reverse suffix
  let l = i + 1, r = nums.length - 1;
  while (l < r) {
    [nums[l], nums[r]] = [nums[r], nums[l]];
    l++; r--;
  }
}

Tradeoff: Linear time, in-place. The pivot is the rightmost index where the ascending suffix breaks; swapping with the smallest greater element + reversing yields the lex-next.

Snowflake-specific tips

Snowflake interviewers want the three-step algorithm stated cleanly before code. Bonus signal: explain why reversing the suffix works (after the swap, the suffix is still descending, so reverse = sort ascending — the smallest continuation).

Common mistakes

  • Off-by-one finding the pivot (using > instead of >= when scanning right-to-left).
  • Sorting the suffix instead of reversing — same result but O(n log n) instead of O(n).
  • Forgetting the 'no pivot found' case (input is fully descending) — must reverse the whole array.

Follow-up questions

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

  • Permutations (LC 46) — generate all.
  • Previous Permutation.
  • Kth Permutation (LC 60).

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 reverse instead of sort the suffix?

After the swap, the suffix is still in descending order. Reversing it converts to ascending = sorted = smallest continuation, in O(n) instead of O(n log n).

What if no pivot exists?

The array is fully descending (lex-largest). The problem says wrap to ascending — the reverse step handles this if you set i = -1 and reverse the whole array.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →