Skip to main content

40. Next Permutation

mediumAsked at Datadog

Rearrange numbers into the lexicographically next greater permutation. Datadog uses this as a deep array-manipulation question — the algorithmic clarity is similar to the cursor-advance logic in their iterator-based query layer.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite for senior roles.

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 arrangement exists, it must be rearranged to the lowest possible order (ascending). Replace nums with its next permutation in place using 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, find next

Enumerate, sort, find current, return successor.

Time
O(n! * n)
Space
O(n! * n)
// Generate all permutations, sort lexically, find current, return successor.
// Factorial — never ship.

Tradeoff: Factorial blows up immediately. Anti-pattern.

2. Knuth's three-step in-place (optimal)

1) Find largest i where nums[i] < nums[i+1]. 2) Find largest j > i where nums[j] > nums[i]. 3) Swap and reverse nums[i+1..].

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

Tradeoff: O(n) time, O(1) space — the canonical algorithm. Each step has a clear purpose; together they produce the next lex permutation.

Datadog-specific tips

Datadog grades on whether you articulate EACH of the three steps with a justification: find pivot (largest decreasing suffix), find swap partner (smallest greater value in suffix), reverse suffix (which is now still in descending order). Without the reasoning, the code looks magical.

Common mistakes

  • Off-by-one in the pivot-find loop — should be largest i where nums[i] < nums[i+1].
  • Using strict > vs >= for the partner search — duplicates trip this up.
  • Forgetting the reverse step — would give 'a' next permutation but not the LEXICOGRAPHICALLY next.

Follow-up questions

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

  • Permutations (LC 46) — generate all.
  • Previous Permutation — symmetric (reverse the comparisons).
  • kth Permutation Sequence (LC 60) — direct construction without enumeration.

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. To make it lex smallest, reverse it — sorting would be O(n log n) for the same result.

What if no next permutation exists?

The pivot-find loop falls through (i = -1), we skip the swap, and reverse the entire array. That gives the smallest permutation, as required.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →