Practice/Amazon/Leetcode 31. Next Permutation

Leetcode 31. Next Permutation

CodingMust

Problem

Given an array of integers, modify it in-place to represent the next permutation in lexicographic order. If the array represents the largest possible permutation, rearrange it to the smallest permutation (sorted in ascending order).

A permutation's lexicographic ordering follows dictionary order: for example, [1, 2, 3] comes before [1, 3, 2], which comes before [2, 1, 3].

Your solution must use only constant extra space and modify the input array directly.

Requirements

1. Transform the array in-place to its next lexicographic permutation
2. If no larger permutation exists (array is in descending order), wrap to the smallest (ascending order)
3. Use only O(1) extra space (excluding the input array)
4. The function should not return anything; modify the input array directly

Constraints

• 1 ≤ nums.length ≤ 100
• 0 ≤ nums[i] ≤ 100
• Time complexity: O(n)
• Space complexity: O(1)

Examples

Example 1:

Input: nums = [1, 2, 3] Output: [1, 3, 2] Explanation: The next permutation after [1, 2, 3] is [1, 3, 2]

Example 2:

Input: nums = [3, 2, 1] Output: [1, 2, 3] Explanation: [3, 2, 1] is the maximum permutation, so wrap to minimum [1, 2, 3]

Example 3:

Input: nums = [1, 1, 5] Output: [1, 5, 1] Explanation: Even with duplicates, find the next lexicographic arrangement

Example 4:

Input: nums = [1, 3, 2] Output: [2, 1, 3] Explanation: Swap the pivot (1) with the smallest larger element (2), then reverse the suffix