Compute the next lexicographic permutation

Q: Compute the next lexicographic permutation

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

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

nums = [1,2,3] → after update: [1,3,2]
nums = [3,2,1] → after update: [1,2,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] ).