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. Given the following Python code for generating parentheses, what is the content of result after calling generateParenthesis(2)?

easy

A. ['((', '))']

B. ['()()', '(())']

C. ['(())', '()()']

D. ['()()', '(()']

Solution

1. Step 1: Trace backtrack calls for n=2

   Sequences generated are '(())' and '()()' in that order due to DFS with backtracking.

2. Step 2: Confirm order and validity

   Both sequences are valid balanced parentheses of length 4, matching expected output.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches known valid sequences for n=2 [OK]

Hint: Backtracking generates sequences in DFS order [OK]

Common Mistakes:

• Confusing order of sequences
• Including invalid partial sequences

2. What is the time complexity of generating all permutations of an array of length n using Heap's algorithm, and why might a common misconception about this complexity be incorrect?

medium

A. O(n! * n^2) because each permutation requires n swaps and there are n! permutations

B. O(n! * log n) because Heap's algorithm uses a heap data structure internally

C. O(n! * n) because each of the n! permutations requires copying the array of length n

D. O(n! + n) because generating permutations is factorial plus linear overhead

Solution

1. Step 1: Identify number of permutations

   There are n! permutations for an array of length n.

2. Step 2: Analyze cost per permutation

   Heap's algorithm generates each permutation with O(1) swaps, but copying the current permutation to the result list takes O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Time complexity is O(n! * n) due to copying each permutation [OK]

Hint: Copying each permutation costs O(n), not the swaps themselves [OK]

Common Mistakes:

• Assuming swaps cost O(n) each or confusing heap data structure usage

3. What is the time complexity of the optimal iterative backtracking solution with pruning for restoring IP addresses from a string of length n, and why?

medium

A. O(3^4) because each of the 4 segments can be length 1 to 3, and pruning limits exploration

B. O(4^n) because each character can start a new segment or continue the previous one

C. O(n^4) because we try all partitions of the string into 4 segments

D. O(n!) due to permutations of segment lengths

Solution

1. Step 1: Identify branching factor per segment

   Each segment can be length 1, 2, or 3, so branching factor is at most 3 per segment.

2. Step 2: Calculate total combinations

   There are 4 segments, so total combinations are at most 3^4 = 81. Pruning further reduces this.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time complexity depends on fixed 4 segments with max 3 choices each [OK]

Hint: Fixed 4 segments with max 3 lengths each -> 3^4 complexity [OK]

Common Mistakes:

• Assuming complexity depends on n^4
• Confusing permutations with combinations

4. Suppose you want to generate all valid parentheses sequences of length 2n, but now you can reuse parentheses pairs multiple times (i.e., sequences can contain repeated pairs). Which modification to the backtracking algorithm correctly handles this variant?

hard

A. Use memoization to store and reuse previously generated valid sequences to handle repeated pairs

B. Keep the original constraints but allow adding '(' or ')' even if counts exceed n, then filter duplicates after generation

C. Modify the algorithm to generate sequences of length 2n without constraints, then check validity and uniqueness

D. Remove the limit on open_count and close_count, allowing unlimited '(' and ')' additions

Solution

1. Step 1: Understand reuse requirement

   Reusing pairs means sequences can contain repeated valid substrings; naive pruning breaks this.

2. Step 2: Analyze modifications

   Removing limits or generating all sequences leads to invalid or duplicate sequences. Memoization allows reusing computed valid sequences efficiently.

3. Step 3: Choose correct approach

   Memoization stores and reuses valid subsequences, enabling correct generation with reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Memoization handles reuse without generating invalid sequences [OK]

Hint: Memoization enables reuse without invalid sequences [OK]

Common Mistakes:

• Removing constraints causes invalid sequences
• Filtering duplicates after generation is inefficient

5. Suppose the problem is modified so that digits can be repeated any number of times (reuse allowed), and you want to generate all letter combinations of length n from the given digits. Which modification to the algorithm correctly handles this reuse scenario?

hard

A. Modify backtracking to allow choosing the same digit multiple times by not incrementing the index after each choice until length n is reached

B. Sort digits and generate combinations by picking letters only once per digit

C. Use dynamic programming to store combinations of length k and build up to length n without reuse

D. Use the same iterative queue approach but do not advance the digit index; instead, for each combination, append letters from all digits repeatedly until length n is reached

Solution

1. Step 1: Understand reuse requirement

   Allowing reuse means digits can be chosen multiple times to build combinations of length n.

2. Step 2: Identify correct approach

   Backtracking can be modified to not increment the digit index after choosing a letter, allowing reuse until length n is reached.

3. Step 3: Why other options fail

   Iterative queue approach as-is assumes fixed digit positions; DP without reuse does not handle repeated digits; sorting and picking once per digit ignores reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backtracking with flexible index handles reuse elegantly [OK]

Hint: Backtracking index controls reuse by not advancing [OK]

Common Mistakes:

• Trying to reuse digits in iterative approach without index control
• Ignoring reuse in DP or sorting