Next Permutation

▶

Steps

setup

Initialize pointer i to find pivot

Set pointer i to the second last index (1) to start scanning from right to left to find the pivot where nums[i] < nums[i+1].

💡 Starting from the right helps find the first place where the sequence stops increasing, which is the pivot point for the next permutation.

Line:

i = len(nums) - 2

💡 The pivot is the first element from the right that can be increased to get the next permutation.

compare

Check if nums[i] >= nums[i+1], move i left if true

Compare nums[1] (2) and nums[2] (3). Since 2 < 3, the condition nums[i] >= nums[i+1] is false, so stop moving i.

💡 This comparison finds the pivot where the sequence stops increasing from the right.

Line:

while i >= 0 and nums[i] >= nums[i + 1]:
    i -= 1

💡 Pivot found at index 1 where nums[i] < nums[i+1].

setup

Initialize pointer j to find successor

Set pointer j to the last index (2) to find the rightmost successor to pivot that is greater than nums[i].

💡 The successor is the smallest number larger than the pivot to swap with for the next permutation.

Line:

j = len(nums) - 1

💡 Starting from the right ensures the successor is the rightmost element greater than pivot.

compare

Check if nums[j] <= nums[i], move j left if true

Compare nums[2] (3) and nums[1] (2). Since 3 > 2, the condition nums[j] <= nums[i] is false, so stop moving j.

💡 We want the rightmost element greater than pivot to swap with.

Line:

while nums[j] <= nums[i]:
    j -= 1

💡 Successor found at index 2.

swap

Swap pivot and successor

Swap the values at indices i (1) and j (2), swapping 2 and 3 to move closer to the next permutation.

💡 Swapping pivot with successor increases the permutation minimally.

Line:

nums[i], nums[j] = nums[j], nums[i]

💡 After swap, prefix is fixed and suffix needs reversal to get next permutation.

setup

Initialize pointers left and right for suffix reversal

Set left to i+1 (2) and right to last index (2) to reverse the suffix after pivot.

💡 Reversing the suffix puts it in ascending order for the next permutation.

Line:

left, right = i + 1, len(nums) - 1

💡 Suffix starts at index 2 and ends at index 2, currently a single element.

compare

Check if left < right to reverse suffix

Compare left (2) and right (2). Since left is not less than right, no reversal needed.

💡 If suffix length is 1 or 0, it is already reversed.

Line:

while left < right:

💡 Suffix is already in ascending order after swap.

move_left|move_right

Confirm no swap needed for suffix reversal

Since left is not less than right, no swap or pointer movement occurs; suffix reversal is complete.

💡 No pointer moves or swaps means suffix is already in correct order.

Line:

while left < right:
    # no iterations since condition false

💡 Suffix reversal loop skipped as suffix length is 1.

reconstruct

Next permutation complete

The array now represents the next permutation [1,3,2]. The algorithm finishes here.

💡 The final array is the next lexicographical permutation after the input.

Line:

return (implicit after reversal)

💡 Next permutation found without generating all permutations.

reconstruct

Read final answer

The final array [1,3,2] is the next permutation after [1,2,3].

💡 This is the output the algorithm produces for the given input.

Line:

print(arr)  # Output: [1,3,2]

💡 The algorithm successfully computed the next permutation in-place.

def next_permutation(nums):
    i = len(nums) - 2  # STEP 1: Initialize i
    while i >= 0 and nums[i] >= nums[i + 1]:  # STEP 2: Find pivot
        i -= 1
    if i >= 0:
        j = len(nums) - 1  # STEP 3: Initialize j
        while nums[j] <= nums[i]:  # STEP 4: Find successor
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]  # STEP 5: Swap pivot and successor
    left, right = i + 1, len(nums) - 1  # STEP 6: Initialize left and right
    while left < right:  # STEP 7: Reverse suffix
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

if __name__ == '__main__':
    arr = [1,2,3]
    next_permutation(arr)  # STEP 8: Compute next permutation
    print(arr)  # STEP 9: Output result

📊

Next Permutation - Watch the Algorithm Execute, Step by Step

Watching each pointer move and swap helps you understand how the algorithm transforms the array in-place to the next permutation without generating all permutations.

setup

1

0

i

2

1

3

2

compare

1

0

i

2

1

3

2

setup

1

0

i

2

1

j

3

2

compare

1

0

i

2

1

j

3

2

swap

1

0

i

3

1

j

2

2

setup

1

0

3

1

right

2

2

compare

1

0

3

1

right

2

2

move_left

1

0

3

1

right

2

2

reconstruct

1

0

3

1

2

2

Result: [1,3,2]

reconstruct

1

0

3

1

2

2

Result: [1,3,2]

Key Takeaways

✓ The pivot is the first element from the right that breaks the descending order.

This is hard to see from code alone because the while loop hides the scanning process.

✓ Swapping the pivot with the rightmost successor greater than it ensures the next permutation is just one step higher.

Visualizing the pointers shows why the successor must be the rightmost element greater than the pivot.

✓ Reversing the suffix after the pivot places it in ascending order, completing the next permutation.

Without visualization, it's not obvious why reversing the suffix is necessary after swapping.

Practice

1. You are given a string containing parentheses and letters. The goal is to remove the minimum number of parentheses to make the string valid (balanced parentheses) and return all possible results. Which algorithmic approach guarantees finding all valid strings with the minimum removals efficiently?

easy

A. Greedy approach that removes invalid parentheses from left to right without backtracking

B. Dynamic Programming that counts valid substrings and reconstructs solutions

C. Breadth-First Search (BFS) that explores all strings by removing one parenthesis at a time level-by-level

D. Brute force generating all subsequences and checking validity

Solution

1. Step 1: Understand problem constraints

   The problem requires minimal removals and all valid results, so partial or greedy removal may miss some minimal solutions.

2. Step 2: Analyze BFS approach

   BFS explores all strings by removing one parenthesis at a time, level-by-level, ensuring the first valid strings found have minimal removals and all such strings are collected.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   BFS guarantees minimal removals and completeness [OK]

Hint: Minimal removals require level-by-level BFS [OK]

Common Mistakes:

• Greedy misses some minimal solutions
• Brute force is correct but inefficient
• DP doesn't apply directly here

2. Identify the bug in the following code snippet for counting beautiful arrangements:

medium

A. Line with 'bit = 1 << num' bit shift

B. Line with 'if (used & bit) == 0' check

C. Line with 'if pos > n:' condition

D. Line with recursive call 'backtrack(pos + 1, used | bit)'

Solution

1. Step 1: Analyze bit shift operation

   Bitmask uses 0-based indexing, so bit for number num should be 1 << (num - 1), not 1 << num.

2. Step 2: Consequence of incorrect bit shift

   Incorrect bit shifts cause wrong bits to be set/checked, leading to missing or duplicate counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct bit shift is critical for accurate used-state tracking [OK]

Hint: Bit shifts must be zero-based for bitmask [OK]

Common Mistakes:

• Off-by-one bit shifts
• Forgetting to unmark used numbers

3. Consider the following code snippet intended to generate unique permutations of an array with duplicates. Which line contains a subtle bug that causes duplicate permutations to be generated?

def permuteUnique(nums):
    nums.sort()
    res = []
    def backtrack(start=0):
        if start == len(nums):
            res.append(nums[:])
            return
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
    backtrack()
    return res

medium

A. Line with 'if i > start and nums[i] == nums[i-1]: continue' (duplicate skipping condition)

B. Line with 'nums.sort()' (sorting input before recursion)

C. Line with 'nums[start], nums[i] = nums[i], nums[start]' before recursion (swap)

D. Line with 'for i in range(start, len(nums)):' (iteration over indices)

Solution

1. Step 1: Analyze duplicate skipping condition

   The condition 'if i > start and nums[i] == nums[i-1]: continue' attempts to skip duplicates but does not consider whether the previous duplicate was used, causing some duplicates to be missed.

2. Step 2: Verify other lines

   Sorting input is correct; swapping before and after recursion is correct; iteration over indices is standard. The bug is in the duplicate skipping logic.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect duplicate skipping causes duplicate permutations [OK]

Hint: Skipping duplicates requires tracking usage, not just comparing adjacent elements [OK]

Common Mistakes:

• Skipping duplicates by only comparing adjacent elements without usage tracking

4. Examine the following code snippet for the Word Search problem. It is almost correct but contains one subtle bug. Identify the line causing the bug.

medium

A. Line where board[r][c] = temp is restored after recursion

B. Line where temp = board[r][c]

C. Line where directions are defined

D. Line missing board[r][c] = '#' to mark visited

Solution

1. Step 1: Identify missing visited marking

   The code does not mark the current cell as visited before recursive calls, allowing revisits.

2. Step 2: Understand impact of missing marking

   Without marking, dfs can revisit the same cell multiple times, causing incorrect matches or infinite loops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Marking visited cells is essential to prevent reuse [OK]

Hint: Check if visited cells are marked before recursion [OK]

Common Mistakes:

• Forgetting to mark visited cells
• Restoring cell too early

5. Suppose the problem is modified so that IP address segments can be reused multiple times (i.e., segments can overlap and be repeated). Which modification to the backtracking algorithm correctly handles this variant without generating duplicates or invalid IPs?

hard

A. Remove the pruning condition on remaining characters and segments to allow overlapping segments

B. Use a memoization cache keyed by (start, segments formed) to avoid recomputing paths

C. Allow segments to be reused by resetting start index to previous segment start after each addition

D. Change the algorithm to generate all permutations of segments without pruning

Solution

1. Step 1: Understand reuse implies overlapping segments

   Allowing reuse means the same substring can be used multiple times, potentially causing repeated computations.

2. Step 2: Apply memoization to avoid duplicates

   Memoization keyed by (start, segments formed) prevents recomputing the same subproblems and avoids duplicates.

3. Step 3: Evaluate other options

   Removing pruning causes inefficiency; resetting start index breaks segment order; generating all permutations ignores validity and pruning.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Memoization efficiently handles reuse without duplicates [OK]

Hint: Memoization avoids recomputation when segments can be reused [OK]

Common Mistakes:

• Removing pruning causes timeouts
• Resetting start index breaks segment order