Permutations

▶

Steps

setup

Initialize result and counters

The algorithm starts by copying the input array [1,2,3] into the results list and initializing the counters array c with zeros for each element.

💡 This setup is crucial because the counters track how many times each element has been swapped, enabling the algorithm to generate permutations without recursion.

Line:

res = [nums[:]]
c = [0] * len(nums)
i = 0

💡 The initial permutation is always included, and counters start at zero to track swaps per element.

compare

Check counter c[0] < 0 (i=0)

The algorithm checks if c[0] < 0, which is false since c[0] = 0 and 0 is not less than 0, so it moves to reset c[0] and increment i.

💡 This comparison determines whether to perform a swap or move to the next index; since c[0] is not less than i, no swap occurs here.

Line:

if c[i] < i:

💡 When counters equal or exceed i, the algorithm resets the counter and moves forward, controlling swap frequency.

shrink

Reset counter c[0] and increment i to 1

Since no swap was done at i=0, the algorithm resets c[0] to 0 (already zero) and increments i to 1 to check the next position.

💡 Resetting counters and moving forward ensures the algorithm explores swaps at higher indices systematically.

Line:

else:
    c[i] = 0
    i += 1

💡 Incrementing i moves the algorithm to consider swaps involving the next element.

compare

Check counter c[1] < 1 (i=1)

The algorithm checks if c[1] < 1, which is true since c[1] = 0, so it proceeds to perform a swap based on i's parity.

💡 This condition triggers a swap to generate a new permutation by exchanging elements at positions 0 and 1 because i is odd/even.

Line:

if c[i] < i:

💡 Counters control when swaps happen, ensuring each element is swapped the correct number of times.

insert

Swap nums[c[1]] and nums[1] because i is odd

Since i=1 is odd, swap elements at indices c[1]=0 and i=1, swapping nums[0] and nums[1], changing array to [2,1,3].

💡 Swapping elements creates a new permutation; the parity of i determines which elements to swap for systematic coverage.

Line:

if i % 2 == 0:
    nums[0], nums[i] = nums[i], nums[0]
else:
    nums[c[i]], nums[i] = nums[i], nums[c[i]]

💡 Parity-based swapping ensures all permutations are generated without repetition.

insert

Add new permutation [2,1,3] to results

After swapping, the new permutation [2,1,3] is appended to the results list.

💡 Each swap produces a unique permutation that must be saved to the results for the final output.

Line:

res.append(nums[:])

💡 Storing a copy of the current array state preserves the permutation before further changes.

shrink

Increment counter c[1] and reset i to 0

The counter c[1] is incremented from 0 to 1, and i is reset to 0 to restart the process from the beginning.

💡 Incrementing counters tracks how many swaps have been done at each position; resetting i restarts the iteration to explore new swaps.

Line:

c[i] += 1
i = 0

💡 Resetting i ensures the algorithm revisits earlier positions to generate all permutations systematically.

compare

Check counter c[0] < 0 (i=0) again

At i=0, the algorithm checks if c[0] < 0, which is false, so it resets c[0] and increments i to 1 again.

💡 This step repeats the initial check to continue the permutation generation cycle.

Line:

if c[i] < i:

💡 The algorithm cycles through indices, checking counters to decide swaps or increments.

shrink

Reset counter c[0] and increment i to 1

No swap at i=0, so c[0] is reset to 0 and i increments to 1 to check the next position.

💡 This step moves the algorithm forward to explore swaps at i=1 again.

Line:

else:
    c[i] = 0
    i += 1

💡 Incrementing i advances the algorithm's exploration of permutations.

compare

Check counter c[1] < 1 (i=1) again

Now c[1] = 1, which is not less than i=1, so no swap occurs; the algorithm resets c[1] and increments i to 2.

💡 This check prevents repeated swaps at the same position beyond allowed times.

Line:

if c[i] < i:

💡 Counters limit swaps to ensure all permutations are unique and complete.

shrink

Reset counter c[1] and increment i to 2

Since no swap at i=1, c[1] is reset to 0 and i increments to 2 to check swaps at the last index.

💡 Moving to the last index allows the algorithm to explore final swaps for permutations.

Line:

else:
    c[i] = 0
    i += 1

💡 Incrementing i to the last index prepares for final swaps in the permutation sequence.

compare

Check counter c[2] < 2 (i=2)

The algorithm checks if c[2] < 2, which is true since c[2] = 0, so it proceeds to swap elements based on i's parity.

💡 This condition triggers swaps involving the last element to generate new permutations.

Line:

if c[i] < i:

💡 Swaps at the last index complete the permutation generation cycle.

insert

Swap nums[0] and nums[2] because i is even

Since i=2 is even, swap elements at indices 0 and 2, changing array from [2,1,3] to [3,1,2].

💡 Parity-based swapping continues to generate new permutations by exchanging elements at strategic positions.

Line:

if i % 2 == 0:
    nums[0], nums[i] = nums[i], nums[0]

💡 Swapping the first and last elements creates a new permutation distinct from previous ones.

insert

Add new permutation [3,1,2] to results

The new permutation [3,1,2] is appended to the results list after the swap.

💡 Each new permutation must be saved immediately to preserve the sequence generated by swaps.

Line:

res.append(nums[:])

💡 Appending a copy of the current array state ensures the permutation is recorded before further changes.

shrink

Increment counter c[2] and reset i to 0

Counter c[2] is incremented from 0 to 1, and i is reset to 0 to restart the iteration from the beginning.

💡 Incrementing counters and resetting i allows the algorithm to explore new swaps from the start.

Line:

c[i] += 1
i = 0

💡 This control flow ensures all permutations are generated by revisiting earlier indices.

compare

Check counter c[0] < 0 (i=0) again

At i=0, c[0] < 0 is false, so the algorithm resets c[0] and increments i to 1.

💡 This repeated check controls the iteration flow through the array indices.

Line:

if c[i] < i:

💡 The algorithm cycles through indices, checking counters to decide swaps or increments.

shrink

Reset counter c[0] and increment i to 1

No swap at i=0, so c[0] is reset and i increments to 1 to check the next position.

💡 Incrementing i advances the algorithm's exploration of permutations.

Line:

else:
    c[i] = 0
    i += 1

💡 Incrementing i moves the algorithm forward systematically.

compare

Check counter c[1] < 1 (i=1)

At i=1, c[1] = 0 which is less than 1, so the algorithm will perform a swap.

💡 This triggers a swap to generate a new permutation by exchanging elements at positions 0 and 1.

Line:

if c[i] < i:

💡 Counters control when swaps happen, ensuring each element is swapped the correct number of times.

insert

Swap nums[c[1]] and nums[1] because i is odd

Since i=1 is odd, swap elements at indices c[1]=0 and i=1, swapping nums[0] and nums[1], changing array to [1,3,2].

💡 Swapping elements creates a new permutation; the parity of i determines which elements to swap for systematic coverage.

Line:

else:
    nums[c[i]], nums[i] = nums[i], nums[c[i]]

💡 Parity-based swapping ensures all permutations are generated without repetition.

insert

Add new permutation [1,3,2] to results

The new permutation [1,3,2] is appended to the results list after the swap.

💡 Each new permutation must be saved immediately to preserve the sequence generated by swaps.

Line:

res.append(nums[:])

💡 Appending a copy of the current array state ensures the permutation is recorded before further changes.

from typing import List

def permute(nums: List[int]) -> List[List[int]]:
    res = [nums[:]]  # STEP 1: Initialize result with original array
    c = [0] * len(nums)  # STEP 1: Initialize counters
    i = 0  # STEP 1: Start index
    while i < len(nums):  # STEP 2-20: Loop through indices
        if c[i] < i:  # STEP 2,4,10,12,18: Check if swap needed
            if i % 2 == 0:  # STEP 5,13: Even index swap
                nums[0], nums[i] = nums[i], nums[0]  # STEP 5,13: Swap elements
            else:  # STEP 5,19: Odd index swap
                nums[c[i]], nums[i] = nums[i], nums[c[i]]  # STEP 5,19: Swap elements
            res.append(nums[:])  # STEP 6,14,20: Append new permutation
            c[i] += 1  # STEP 7,15: Increment counter
            i = 0  # STEP 7,15: Reset index
        else:  # STEP 3,9,11,17: Reset counter and increment index
            c[i] = 0
            i += 1
    return res

if __name__ == '__main__':
    print(permute([1,2,3]))

📊

Permutations - Watch the Algorithm Execute, Step by Step

Watching each swap and counter update reveals how Heap's algorithm efficiently produces permutations without recursion, making the process clear and intuitive.

enteringnums=[1,2,3]

Call Path (current → root)

permute([1,2,3])

Found 1: [1,2,3]

choosingnums=[1,2,3]

Call Path (current → root)

permute([1,2,3])

Tried

no swap at i=0

Remaining

reset c[0], increment i

Found 1: [1,2,3]

backtrackingnums=[1,2,3]

Call Path (current → root)

permute([1,2,3])

Tried

reset c[0], increment i

Remaining

check c[1] < 1

Found 1: [1,2,3]

choosingnums=[1,2,3]

Call Path (current → root)

permute([1,2,3])

Tried

swap at i=1

Found 1: [1,2,3]

choosingnums=[2,1,3]

Call Path (current → root)

permute([1,2,3])

Tried

swap nums[0] and nums[1]

Found 1: [1,2,3]

backtrackingnums=[2,1,3]

Call Path (current → root)

permute([1,2,3])

Tried

added [2,1,3]

Found 2: [1,2,3] [2,1,3]

backtrackingnums=[2,1,3]

Call Path (current → root)

permute([1,2,3])

Tried

increment c[1], reset i

Remaining

check c[0] < 0

Found 2: [1,2,3] [2,1,3]

choosingnums=[2,1,3]

Call Path (current → root)

permute([1,2,3])

Tried

no swap at i=0

Remaining

reset c[0], increment i

Found 2: [1,2,3] [2,1,3]

backtrackingnums=[2,1,3]

Call Path (current → root)

permute([1,2,3])

Tried

reset c[0], increment i

Remaining

check c[1] < 1

Found 2: [1,2,3] [2,1,3]

choosingnums=[2,1,3]

Call Path (current → root)

permute([1,2,3])

Tried

no swap at i=1

Remaining

reset c[1], increment i

Found 2: [1,2,3] [2,1,3]

backtrackingnums=[2,1,3]

Call Path (current → root)

permute([1,2,3])

Tried

reset c[1], increment i

Remaining

check c[2] < 2

Found 2: [1,2,3] [2,1,3]

choosingnums=[2,1,3]

Call Path (current → root)

permute([1,2,3])

Tried

swap at i=2

Found 2: [1,2,3] [2,1,3]

choosingnums=[3,1,2]

Call Path (current → root)

permute([1,2,3])

Tried

swap nums[0] and nums[2]

Found 2: [1,2,3] [2,1,3]

backtrackingnums=[3,1,2]

Call Path (current → root)

permute([1,2,3])

Tried

added [3,1,2]

Found 3: [2,1,3] [3,1,2]

backtrackingnums=[3,1,2]

Call Path (current → root)

permute([1,2,3])

Tried

increment c[2], reset i

Remaining

check c[0] < 0

Found 3: [2,1,3] [3,1,2]

choosingnums=[3,1,2]

Call Path (current → root)

permute([1,2,3])

Tried

no swap at i=0

Remaining

reset c[0], increment i

Found 3: [2,1,3] [3,1,2]

backtrackingnums=[3,1,2]

Call Path (current → root)

permute([1,2,3])

Tried

reset c[0], increment i

Remaining

check c[1] < 1

Found 3: [2,1,3] [3,1,2]

choosingnums=[3,1,2]

Call Path (current → root)

permute([1,2,3])

Tried

swap at i=1

Found 3: [2,1,3] [3,1,2]

choosingnums=[1,3,2]

Call Path (current → root)

permute([1,2,3])

Tried

swap nums[0] and nums[1]

Found 3: [2,1,3] [3,1,2]

backtrackingnums=[1,3,2]

Call Path (current → root)

permute([1,2,3])

Tried

added [1,3,2]

Found 4: [3,1,2] [1,3,2]

Key Takeaways

✓ Heap's algorithm uses counters and parity-based swaps to generate all permutations efficiently without recursion.

This insight is hard to see from code alone because the counters' role and parity-based swapping logic are subtle and intertwined.

✓ The counters array controls how many times each element is swapped, ensuring no duplicate permutations and systematic coverage.

Understanding counters' gating role clarifies why the algorithm resets and increments indices, which is not obvious from reading code.

✓ Swapping elements based on whether the current index is even or odd ensures all permutations are generated by minimal swaps.

The parity-based swap decision is a key branching point that determines the swap pattern, which is clearer when visualized step-by-step.

Practice

1. What is the time complexity of the optimal iterative approach using a queue to generate all letter combinations for a digit string of length n, assuming each digit maps to at most 4 letters?

medium

A. O(n * 4^n) because we process each digit and expand combinations exponentially

B. O(2^n) because each digit doubles the number of combinations

C. O(4^n * n) because there are up to 4^n combinations and each combination is built with n concatenations

D. O(n^2) because we process n digits and each combination takes n steps

Solution

1. Step 1: Identify number of combinations

   Each digit maps to up to 4 letters, so total combinations are up to 4^n.

2. Step 2: Analyze work per combination

   Each combination is built by concatenating letters for n digits, so each combination requires O(n) time to build.

3. Step 3: Simplify complexity expression

   O(4^n * n) and O(n * 4^n) are equivalent; however, O(n * 4^n) because we process each digit and expand combinations exponentially is the standard notation emphasizing processing each digit and expanding combinations exponentially.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Time is exponential in n with linear cost per combination [OK]

Hint: Exponential combinations times linear build cost [OK]

Common Mistakes:

• Confusing exponential base (2 vs 4)
• Ignoring concatenation cost per combination

2. What is the time complexity of the optimal palindrome partitioning algorithm that uses backtracking with dynamic palindrome checks by expanding around centers for palindrome verification on a string of length n?

medium

A. O(n^2) because palindrome checks are done in constant time using DP

B. O(n^3) due to checking all substrings and palindrome verification

C. O(2^n) since all partitions are generated without extra palindrome checks

D. O(n * 2^n) because each character can start a partition and palindrome checks are O(n)

Solution

1. Step 1: Identify number of partitions

   There are up to 2^(n-1) ways to partition a string of length n.

2. Step 2: Analyze palindrome check cost

   Using expand around center, palindrome check per substring is O(n) worst case, done during backtracking.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Combining partitions and palindrome checks yields O(n * 2^n) [OK]

Hint: Partitions grow exponentially; palindrome checks add linear factor [OK]

Common Mistakes:

• Assuming palindrome checks are O(1) without DP
• Confusing total partitions with time complexity
• Ignoring recursion stack space

3. Identify the bug in the following code snippet for getPermutation:

medium

A. Line 6: k is not converted to zero-based index before calculations.

B. Line 2: factorial array initialization is incorrect.

C. Line 10: The index calculation uses integer division incorrectly.

D. Line 12: numbers.pop(idx) should be numbers.remove(idx).

Solution

1. Step 1: Check k adjustment

   k must be decremented by 1 to convert to zero-based indexing before using factorial divisions.

2. Step 2: Understand impact of missing k -= 1

   Without this, idx calculation is off by one, leading to incorrect permutation output.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing k -= 1 causes wrong indexing and wrong permutation [OK]

Hint: Always convert k to zero-based before factorial indexing [OK]

Common Mistakes:

• Forgetting zero-based index adjustment
• Misusing pop vs remove
• Incorrect factorial initialization

4. What is the time complexity of the optimal backtracking with Trie approach for Word Search II, given a board of size MxN and a list of words with maximum length L? Assume the Trie is already built.

medium

A. O(M * N * 4 * 3^(L-1)) due to pruning and adjacency constraints

B. O(M * N * 4^L * W), where W is the number of words

C. O(M * N * L^2) because each cell explores all prefixes

D. O(M * N * L) since each cell is visited once per character

Solution

1. Step 1: Identify branching factor in backtracking

   From each cell, up to 4 directions are possible initially, then up to 3 directions for subsequent steps due to no revisiting.

2. Step 2: Calculate complexity with pruning

   Trie pruning reduces unnecessary paths, so complexity is roughly O(M * N * 4 * 3^(L-1)) where L is max word length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches known complexity from Trie + backtracking analysis [OK]

Hint: Branching factor reduces after first step due to visited constraints [OK]

Common Mistakes:

• Confusing W (number of words) as multiplicative factor in optimal approach.

5. Suppose you want to modify the palindrome partitioning algorithm to allow reuse of substrings in partitions (i.e., substrings can appear multiple times in different partitions). Which change to the algorithm is necessary to correctly handle this variant without losing valid partitions or causing duplicates?

hard

A. Memoize palindrome checks and reuse results but keep backtracking unchanged

B. Modify backtracking to avoid popping from path to reuse substrings across calls

C. Use a global visited set to skip substrings already used in previous partitions

D. Allow substrings to be reused by resetting path after each complete partition

Solution

1. Step 1: Understand reuse requirement

   Reusing substrings means substrings can appear multiple times in different partitions, so path management must allow multiple uses.

2. Step 2: Identify necessary algorithm change

   Memoizing palindrome checks improves efficiency by avoiding repeated palindrome computations, while backtracking logic remains unchanged to generate all valid partitions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Memoization optimizes palindrome checks without affecting partition generation correctness [OK]

Hint: Memoize palindrome checks to optimize without changing backtracking [OK]

Common Mistakes:

• Assuming popping affects substring reuse
• Using visited sets that block valid reuse
• Resetting path incorrectly losing partitions