#31

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Next Permutation

Next Permutation is a medium-difficulty problem focusing on generating the next lexicographically greater permutation of integers.

array two pointers

Problem Statement

Given an array of integers, find its next permutation in lexicographical order. If the current permutation is the largest possible, return the smallest permutation. A permutation is an arrangement of numbers in a sequence, and the next permutation is the one that comes after it in sorted order. If no larger permutation exists, return the array sorted in ascending order.

To solve this, we need to identify the largest suffix that is in decreasing order. Once identified, we swap the rightmost element of this suffix with the smallest element from the suffix that is larger than it, and then reverse the suffix. This approach guarantees that the next permutation is generated with minimal changes.

Examples

Example 1

Input: nums = [1,2,3]

Output: [1,3,2]

Example details omitted.

Example 2

Input: nums = [3,2,1]

Output: [1,2,3]

Example details omitted.

Example 3

Input: nums = [1,1,5]

Output: [1,5,1]

Example details omitted.

Constraints

1 <= nums.length <= 100
0 <= nums[i] <= 100

Solution Approach

Identifying the Decreasing Suffix

Scan the array from right to left to find the largest suffix that is in decreasing order. This identifies the point where the permutation stops being in increasing order.

Finding the Swap Candidate

Find the smallest number in the suffix that is greater than the element before the decreasing suffix. This will be the element to swap to get the next greater permutation.

Reversing the Suffix

Once the swap is done, reverse the suffix to ensure the next permutation is the smallest possible arrangement after the swap.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The solution runs in O(n) time because we scan the array once to identify the suffix, perform a swap, and reverse the suffix. The space complexity is O(1) as no additional space is required beyond the input array.

What Interviewers Usually Probe

Checks for efficient in-place manipulation of the array.
Assesses understanding of permutations and their properties.
Tests ability to apply two-pointer techniques and invariant tracking in array problems.

Common Pitfalls or Variants

Common pitfalls

Forgetting to reverse the suffix after swapping.
Not correctly identifying the largest decreasing suffix.
Misunderstanding the termination condition when no next permutation is possible.

Follow-up variants

Generate the previous permutation instead of the next.
Handle larger arrays with more elements.
Optimize the solution for specific types of input arrays.

FAQ

What is the main pattern used in the Next Permutation problem?

The main pattern involves two-pointer scanning with invariant tracking to efficiently generate the next permutation.

How can I ensure that the next permutation is generated correctly?

You must identify the largest decreasing suffix, swap elements appropriately, and reverse the suffix to obtain the next permutation.

What is the time complexity of the Next Permutation algorithm?

The time complexity is O(n) because we scan the array and perform constant-time operations (swap and reverse).

Is the Next Permutation problem solvable in constant space?

Yes, the solution uses O(1) extra space, as the operations are done in-place on the input array.

What is the failure mode of the Next Permutation problem?

The failure mode occurs when the array is in descending order, and the next permutation is the smallest, requiring a complete rearrangement of the array.

terminal

Solution

Solution 1: Two traversals

We first traverse the array from back to front and find the first position $i$ where $nums[i] \lt nums[i + 1]$.

1

2

3

4

5

6

7

8

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        i = next((i for i in range(n - 2, -1, -1) if nums[i] < nums[i + 1]), -1)
        if ~i:
            j = next((j for j in range(n - 1, i, -1) if nums[j] > nums[i]))
            nums[i], nums[j] = nums[j], nums[i]
        nums[i + 1 :] = nums[i + 1 :][::-1]

Continue Practicing

#27 remove element #26 remove duplicates from sorted array #42 trapping rain water