Recommended
Practice
1. Given the following code for next permutation, what is the content of the array
nums after calling next_permutation([1, 3, 2])?easy
Solution
Step 1: Trace the pivot search
Start with i = 1 (index of 3). Since nums[1]=3 >= nums[2]=2, decrement i to 0. nums[0]=1 < nums[1]=3, so pivot i=0.Step 2: Find j to swap with pivot
Start j=2 (value 2). nums[2]=2 > nums[0]=1, so j=2. Swap nums[0] and nums[2]: array becomes [2,3,1]. Then reverse suffix from i+1=1 to end: reverse [3,1] -> [1,3]. Final array: [2,1,3].Final Answer:
Option C -> Option CQuick Check:
Array changes from [1,3,2] to [2,1,3] after next permutation [OK]
Hint: Pivot found at first decreasing from right, swap and reverse suffix [OK]
Common Mistakes:
- Swapping with wrong element
- Not reversing suffix after swap
2. 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
Solution
Step 1: Identify number of combinations
Each digit maps to up to 4 letters, so total combinations are up to 4^n.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.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.Final Answer:
Option A -> Option AQuick 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
3. Consider the following code snippet for palindrome partitioning. Which line contains a subtle bug that causes incorrect or duplicate partitions?
def partition(s):
def is_palindrome(left, right):
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
def backtrack(start, path):
if start == len(s):
result.append(path) # Line X
return
for end in range(start, len(s)):
if is_palindrome(start, end):
path.append(s[start:end+1])
backtrack(end+1, path)
path.pop()
result = []
backtrack(0, [])
return result
medium
Solution
Step 1: Identify how results are stored
Appendingpathdirectly stores a reference, so later modifications affect all stored results.Step 2: Correct approach
Useresult.append(path[:])to append a copy, preserving each partition snapshot.Final Answer:
Option B -> Option BQuick Check:
Shared references cause incorrect final partitions [OK]
Hint: Always append a copy of path to results [OK]
Common Mistakes:
- Forgetting to copy path before appending
- Incorrect palindrome check boundaries
- Forgetting to pop after recursion
4. 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
Solution
Step 1: Identify number of permutations
There are n! permutations for an array of length n.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.Final Answer:
Option C -> Option CQuick 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
5. Suppose the N-Queens problem is modified so that queens can be placed multiple times in the same column (i.e., column constraint is relaxed), but diagonal attacks still apply. Which modification to the bitmask backtracking algorithm correctly adapts to this variant?
hard
Solution
Step 1: Understand relaxed constraints
Since columns can have multiple queens, column bitmask is no longer needed to prune placements.Step 2: Adapt pruning to only diagonal attacks
Keep diag1 and diag2 bitmasks to prune diagonal conflicts, but remove column mask from available_positions calculation.Final Answer:
Option A -> Option AQuick Check:
Removing column mask allows multiple queens per column while still pruning diagonals [OK]
Hint: Relaxed constraints remove column pruning, keep diagonal pruning [OK]
Common Mistakes:
- Resetting column mask each row incorrectly
- Ignoring diagonal pruning
- Using greedy without pruning