Compute the next lexicographic permutation
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Problem
Given an integer array `nums` representing a permutation of its elements, modify the array **in-place** to produce the **next lexicographically greater** permutation.
- If such a permutation exists, rearrange `nums` into that next greater ordering.
- If no greater permutation exists (i.e., `nums` is in non-increasing order), rearrange `nums` into the **lowest possible order** (sorted ascending).
## Input
- `nums`: an array of integers (may contain duplicates).
## Output
- No return value; update `nums` in-place.
## Requirements
- Use **O(1)** extra space.
- Aim for **O(n)** time.
## Examples
1. `nums = [1,2,3]` → after update: `[1,3,2]`
2. `nums = [3,2,1]` → after update: `[1,2,3]`
3. `nums = [1,1,5]` → after update: `[1,5,1]`
## Notes / Edge Cases to consider
- Array length `n` can be 0, 1, or larger.
- Duplicates may exist.
- Strictly increasing, strictly decreasing, and “plateau” patterns (e.g., `[2,2,1]`).
Quick Answer: This question evaluates understanding of permutations and lexicographic ordering, in-place array manipulation, and algorithmic reasoning about time and space constraints, including handling duplicates and edge cases.
Return the next lexicographic permutation of nums, or the lowest sorted order if none exists.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([1,2,3],)
Expected Output: [1, 3, 2]
Explanation: Prompt example 1.
Input: ([3,2,1],)
Expected Output: [1, 2, 3]
Explanation: Wrap to lowest order.
Input: ([1,1,5],)
Expected Output: [1, 5, 1]
Explanation: Duplicates.
Input: ([],)
Expected Output: []
Explanation: Empty array.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.