@meta
title: Next Permutation
questionNo: 3
totalQuestions: 191
sheetLabel: Striver SDE Sheet
sourceLabel: TakeUForward
@endmeta

@page
tag: A
pageNo: 1 / 1
totalPages: 1
@endpage

@section
region: full
title: Problem Statement
content:
Given an array representing a permutation, transform it into the next lexicographically greater permutation.
If such a permutation does not exist, rearrange the numbers into the lowest possible order.
The answer must be done in-place.
@endsection

@section
region: left
title: Examples
content:
Input: nums = [1,2,3]
Output: [1,3,2]
Explanation: [1,3,2] is the smallest permutation larger than [1,2,3].
---
Input: nums = [3,2,1]
Output: [1,2,3]
Explanation: The sequence is already the largest, so we wrap to the smallest.
@endsection

@section
region: right
title: Custom Notes
content:
- Scan from the right to find the first dip.
- Suffix to the right of the dip is always non-increasing.
- Swap with the rightmost just-greater element.
- Then reverse the suffix, do not sort it.
- Memory hook: dip, swap, reverse.
@endsection

@section
region: full
title: Brute Force Approach : TC: SC:
badge: 1 / 3
content:
Algorithm: Generate all permutations, sort them, and locate the next one.
Pseudo:
- Generate every permutation of the array.
- Sort all permutations lexicographically.
- Find the current permutation and return the next one.
Time: O(n! * n)
Space: Huge
Why mention it: It explains the meaning of the task, but is never acceptable in interview implementation.
@endsection

@section
region: full
title: Better Approach : TC: SC:
badge: 2 / 3
content:
Algorithm: Find the break point and sort the suffix after swapping.
Pseudo:
- Find the first index i from the right where nums[i] < nums[i + 1].
- Find the smallest number greater than nums[i] on the right.
- Swap them.
- Sort the suffix from i + 1 to end.
Time: O(n log n)
Space: O(1) extra if the sort is in-place
Interview line: This is acceptable logically, but the suffix is already in descending order, so reverse is enough.
@endsection

@section
region: full
title: Optimal Approach : TC: SC:
badge: 3 / 3
content:
Algorithm: Use one backward scan for the dip, one backward scan for the swap target, then reverse the suffix.
Pseudo:
- Find index i from the right such that nums[i] < nums[i + 1].
- If no such i exists, reverse the whole array and return.
- Find index j from the right such that nums[j] > nums[i].
- Swap nums[i] and nums[j].
- Reverse nums from i + 1 to end.
Time: O(n)
Space: O(1)
Key insight: Reverse works because the suffix is already in descending order before the final step.
@endsection

@section
region: grid
title: PCode
badge: 1 / 3
codeLang: pseudo
content:
allPermutations = generate all permutations of nums
sort allPermutations in lexicographic order

position = index of nums inside allPermutations

IF position is not the last index
    RETURN allPermutations[position + 1]

RETURN allPermutations[0]
@endsection

@section
region: grid
title: PCode
badge: 2 / 3
codeLang: pseudo
content:
i = rightmost index such that nums[i] < nums[i + 1]

IF i does not exist
    sort nums
    RETURN nums

find the smallest value on the right greater than nums[i]
swap it with nums[i]
sort nums from i + 1 to end

RETURN nums
@endsection

@section
region: grid
title: PCode
badge: 3 / 3
codeLang: pseudo
content:
i = rightmost index such that nums[i] < nums[i + 1]

IF i does not exist
    reverse whole array
    RETURN nums

j = rightmost index such that nums[j] > nums[i]
swap nums[i] and nums[j]
reverse nums from i + 1 to end

RETURN nums
@endsection