Next Permutation

MediumArrays & Hashingin-place rearrange

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given an array of integers nums, rearrange its elements into the **next** arrangement in lexicographic order. Think of every distinct ordering of the array's elements as a single entry in a sorted list of all possible permutations. The "next permutation" is the entry that comes immediately after the current one in that ordering. For example, the orderings of [1, 2, 3] in ascending lexicographic order are [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1], so the permutation following [1,2,3] is [1,3,2]. If the array is already the largest possible arrangement (its elements are in descending order), it has no successor, so wrap around to the **smallest** arrangement (its elements in ascending order). For this problem, return the resulting array. A correct in-place approach uses only constant extra memory beyond the input.

Examples

Input: nums = [1, 2, 3]
Output: [1, 3, 2]
Among all orderings of these elements, [1,3,2] is the one immediately after [1,2,3].
Input: nums = [3, 2, 1]
Output: [1, 2, 3]
[3,2,1] is the largest arrangement, so it wraps around to the smallest one, [1,2,3].
Input: nums = [1, 1, 5]
Output: [1, 5, 1]
Duplicate values are allowed; the next distinct ordering is [1,5,1].

Constraints

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100
  • The array may contain duplicate values.
  • Aim for O(n) time and O(1) extra space.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.