## Problem Rearrange an integer array in place into the next lexicographically greater permutation. If the array is already the greatest permutation of its elements, rearrange it into the smallest permutation. ### Function Contract Implement `nextPermutation(values)`. Return the mutated array for testing, but use only `O(1)` auxiliary space. ### Constraints & Assumptions - `0 <= len(values) <= 200,000`. - Values are signed 32-bit integers and may repeat. - Lexicographic order compares elements from left to right. ### Clarifying Questions to Ask - Must the transformation be in place? Yes. - Are duplicates allowed? Yes. - What should empty and single-element arrays do? Remain unchanged. - If no greater permutation exists, should the function signal failure? No, wrap to the smallest permutation. ```hint Find the longest non-increasing suffix The pivot is immediately before that suffix; no larger arrangement exists if the entire array is non-increasing. ``` ```hint Make the smallest possible increase Swap the pivot with the rightmost element strictly greater than it, then reverse the suffix. ``` ### Examples ```text [1, 3, 5, 4, 2] -> [1, 4, 2, 3, 5] [3, 2, 1] -> [1, 2, 3] [1, 1, 5] -> [1, 5, 1] ``` ### Evaluation Focus - Uses strict comparison when duplicates occur. - Correctly handles a fully non-increasing array. - Reverses rather than sorts the suffix. - Runs in `O(n)` time with `O(1)` extra space. ### Extensions to Discuss 1. How would you derive the previous permutation symmetrically? 2. Why is the suffix known to be non-increasing before the swap? 3. How would you compute the k-th next permutation without applying this operation k times?