Practice
1. Consider the following code snippet that rotates a 3x3 matrix by 90 degrees clockwise in-place. After the first iteration of the outer loop (layer = 0) and the first iteration of the inner loop (i = 0), what is the value of
matrix[0][2]?easy
Solution
Step 1: Trace first iteration (layer=0, i=0)
first=0, last=2, offset=0; top=matrix[0][0]=1Step 2: Perform swaps
matrix[0][0] = matrix[2][0] = 7; matrix[2][0] = matrix[2][2] = 9; matrix[2][2] = matrix[0][2] = 3; matrix[0][2] = top = 1Final Answer:
Option A -> Option AQuick Check:
matrix[0][2] updated to 7 after first swap [OK]
Hint: Track swaps carefully to find updated element values [OK]
Common Mistakes:
- Confusing indices during swaps
- Mixing up top and offset calculations
2. You are given a square matrix and asked to transform it so that rows become columns and columns become rows without using extra space. Which approach guarantees an optimal in-place solution?
easy
Solution
Step 1: Understand the problem constraints
The problem requires an in-place transpose of a square matrix, meaning no extra matrix can be used.Step 2: Identify the correct approach
Swapping elements symmetrically across the diagonal once (upper triangle only) ensures each pair is swapped exactly once, achieving in-place transpose efficiently.Final Answer:
Option B -> Option BQuick Check:
Swapping only upper triangle elements avoids double swaps and extra space [OK]
Hint: Swap only upper triangle elements once [OK]
Common Mistakes:
- Using extra space unnecessarily
- Swapping elements twice by iterating entire matrix
- Ignoring diagonal symmetry leading to incorrect results
3. Identify the bug in the following in-place Game of Life code snippet that causes incorrect neighbor counts and final states.
medium
Solution
Step 1: Examine neighbor counting loop
The code checks board[x][y] without verifying if x,y are within valid indices, risking index errors or invalid counts.Step 2: Confirm other parts are correct
Final decoding loop correctly converts 2->0 and 3->1; encoding uses correct integers; neighbor counting excludes dead cells properly.Final Answer:
Option A -> Option AQuick Check:
Missing boundary check causes incorrect neighbor counts or runtime errors [OK]
Hint: Always check boundaries before accessing neighbors [OK]
Common Mistakes:
- Forgetting boundary checks in neighbor loops
- Not finalizing encoded states after first pass
- Misusing encoding integers
4. Identify the bug in the following code snippet for finding lucky numbers in a matrix:
from typing import List
def luckyNumbers(matrix: List[List[int]]) -> List[int]:
m, n = len(matrix), len(matrix[0])
row_mins = [min(row) for row in matrix]
col_maxs = [min(matrix[i][j] for i in range(m)) for j in range(n)] # Bug here
return [matrix[i][j] for i in range(m) for j in range(n) if matrix[i][j] == row_mins[i] == col_maxs[j]]
medium
Solution
Step 1: Analyze column maximum computation
The code uses min(matrix[i][j] for i in range(m)) to compute col_maxs, which is incorrect because it finds the minimum instead of the maximum.Step 2: Understand impact
Using min instead of max causes the algorithm to identify incorrect elements as lucky numbers or miss valid ones.Final Answer:
Option A -> Option AQuick Check:
Column maxs must use max(), not min() [OK]
Hint: Check min vs max carefully in column computations [OK]
Common Mistakes:
- Confusing min and max in column computations
- Ignoring empty matrix edge cases
- Misindexing in list comprehensions
5. Consider this buggy version of the optimal Set Matrix Zeroes code. Which line contains the subtle bug that causes incorrect zeroing in some cases?
def setZeroes(matrix):
m, n = len(matrix), len(matrix[0])
first_row_zero = any(matrix[0][j] == 0 for j in range(n))
first_col_zero = any(matrix[i][0] == 0 for i in range(m))
for i in range(m): # Bug here: starts from 0 instead of 1
for j in range(n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if first_row_zero:
for j in range(n):
matrix[0][j] = 0
if first_col_zero:
for i in range(m):
matrix[i][0] = 0
medium
Solution
Step 1: Identify marking loop range
The marking loop should start from 1 to avoid overwriting first row/column flags prematurely.Step 2: Understand impact
Starting from 0 causes first row/column to be overwritten before flags are saved, losing zero info.Final Answer:
Option A -> Option AQuick Check:
Changing loop to start at 1 fixes the bug [OK]
Hint: Mark zeros starting from index 1 to preserve flags [OK]
Common Mistakes:
- Zeroing first row/column too early
- Incorrect loop ranges causing info loss
- Confusing first pass marking with zeroing pass