Skip to main content

40. Next Permutation

mediumAsked at Workday

Rearrange numbers into the next lexicographically greater permutation. Workday uses this to test array-manipulation discipline — same pattern as cycling shift-assignment rotations.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 onsite.

Problem

A permutation of an array of integers is an arrangement of its members into a sequence or linear order. The next permutation of an array of integers is the next lexicographically greater permutation of its integer. If no such permutation exists, then rearrange to the lowest possible order (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 sort

Enumerate all permutations, sort lexicographically, find next.

Time
O(n!)
Space
O(n!)
// generate all n! perms, sort, find next — only feasible for tiny n

Tradeoff: Factorial blow-up.

2. Pivot + swap + reverse

Find rightmost i with nums[i] < nums[i+1]. Find rightmost j > i with nums[j] > nums[i]. Swap. Reverse suffix from i+1.

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: Single pass. The trick: the suffix after the pivot is non-increasing; reversing it gives the smallest suffix and thus the next-larger arrangement.

Workday-specific tips

Workday wants you to articulate each of the 3 steps before coding. The 'pivot + swap + reverse' formula is the entire solution; getting the order wrong is the failure mode. Mention the all-descending edge case explicitly.

Common mistakes

  • Sorting instead of reversing the suffix.
  • Using >= for the pivot search comparison incorrectly — must be strict <.
  • Not handling the all-descending case (no pivot found) — skip swap, still reverse to sort ascending.

Follow-up questions

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

  • Previous Permutation.
  • Kth Smallest Permutation (LC 60).
  • 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 does this find the next permutation?

After the pivot, the suffix is non-increasing — already the largest arrangement. Swapping the pivot with the smallest larger element in the suffix gives the next jump; reversing the suffix gives the smallest suffix beyond that pivot.

What if input is already the largest permutation?

No pivot found (i = -1). Skip swap; reverse the entire array — produces the smallest (sorted ascending).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →