Skip to main content

40. Next Permutation

mediumAsked at Reddit

Compute the lexicographically next permutation in-place. Reddit asks this rare problem to test in-place manipulation under a non-obvious algorithm — connects to enumerating moderator action sequences in their audit trail.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit on-site question for senior backend roles.

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. Generate all permutations and pick next

Enumerate all permutations sorted, find current, return next.

Time
O(n! * n)
Space
O(n! * n)
// Anti-pattern: generates n! permutations to find one. TLE for n > 8.

Tradeoff: Factorial time. Mention only as the anti-pattern.

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

From the right, find first i where nums[i] < nums[i+1]. Find rightmost j > i with nums[j] > nums[i]. Swap. 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]];
  }
  let l = i + 1, r = nums.length - 1;
  while (l < r) {
    [nums[l], nums[r]] = [nums[r], nums[l]];
    l++; r--;
  }
}

Tradeoff: Linear time, O(1) space. The three-step algorithm is rote-memorize material.

Reddit-specific tips

Reddit interviewers want the three-step algorithm explained verbally before coding. Bonus signal: walk through [1,3,5,4,2]: pivot=3, swap with 4 -> [1,4,5,3,2], reverse suffix -> [1,4,2,3,5].

Common mistakes

  • Forgetting to reverse the suffix (necessary for lex-next).
  • Using <= or < incorrectly when finding j.
  • Not handling the all-descending case (return sorted ascending).

Follow-up questions

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

  • Previous permutation — mirror algorithm.
  • Permutation rank — given a permutation, find its index in sorted order.
  • Kth permutation sequence (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 the suffix instead of sort?

After the pivot swap, the suffix is guaranteed non-increasing. Reverse is O(n); sort would be O(n log n).

What if the array is fully descending?

No valid 'next' — wrap to ascending. The algorithm naturally produces this because i = -1 and the reverse step turns the whole array around.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →