Practice
1. Consider the following Python function that returns the spiral order of a matrix. What is the output of
spiralOrder([[1,2],[3,4]])?easy
Solution
Step 1: Trace first iteration
Top=0, Bottom=1, Left=0, Right=1. Append top row: [1, 2]. Increment top to 1.Step 2: Trace right column and subsequent steps
Append right column from row 1 to 1: [4]. Decrement right to 0. Since top <= bottom, append bottom row reversed: [3]. Decrement bottom to 0. Left <= right, but now left=0, right=0, top=1, bottom=0 so loop ends.Final Answer:
Option B -> Option BQuick Check:
Output matches clockwise spiral traversal [OK]
Hint: Trace boundaries and append order carefully [OK]
Common Mistakes:
- Appending rows or columns in wrong order
- Off-by-one errors in loops
- Not updating boundaries correctly
2. Consider this buggy code snippet for diagonal traversal. Which line contains the subtle bug that causes incorrect traversal or index errors?
def findDiagonalOrder(mat):
if not mat or not mat[0]:
return []
m, n = len(mat), len(mat[0])
result = []
for d in range(m + n - 1):
r_start = max(0, d - n + 1)
r_end = min(d, m - 1)
if d % 2 == 0:
for r in range(r_start, r_end + 1): # Bug here: direction wrong
c = d - r
result.append(mat[r][c])
else:
for r in range(r_end, r_start - 1, -1):
c = d - r
result.append(mat[r][c])
return resultmedium
Solution
Step 1: Identify traversal direction for even diagonals
Even diagonals must traverse from r_end down to r_start (descending).Step 2: Check loop direction in buggy code
The loop uses ascending range from r_start to r_end, which is incorrect and causes wrong order or index errors.Final Answer:
Option B -> Option BQuick Check:
Fixing loop direction restores correct traversal [OK]
Hint: Even diagonals traverse downward (descending indices) [OK]
Common Mistakes:
- Using ascending loop for even diagonals causing order errors
3. What is the time complexity of the optimal in-place Game of Life solution that encodes states using 4 integer values, given an m x n board?
medium
Solution
Step 1: Identify loops and operations
Outer loops iterate over all m*n cells. For each cell, 8 neighbors are checked in constant time.Step 2: Calculate total operations
Total operations = m*n*8 = O(m*n), since 8 is constant.Final Answer:
Option D -> Option DQuick Check:
Neighbor checks are constant per cell -> linear in board size [OK]
Hint: Neighbor checks are constant per cell, so linear overall [OK]
Common Mistakes:
- Mistaking neighbor checks as nested loops over entire board
- Counting neighbor checks twice incorrectly
- Confusing linear scan with quadratic complexity
4. What is the time complexity of the optimal in-place boundary shrinking spiral traversal algorithm for an m x n matrix?
medium
Solution
Step 1: Identify the number of elements visited
The algorithm visits each element exactly once, so total operations scale with m*n.Step 2: Analyze loops and boundary updates
Though boundaries shrink, the total number of elements processed remains m*n, no nested multiplicative overhead beyond that.Final Answer:
Option C -> Option CQuick Check:
Each element processed once -> O(m*n) [OK]
Hint: Count total elements visited, not loop nesting [OK]
Common Mistakes:
- Confusing boundary shrinking loops as nested multiplicative loops
- Ignoring that each element is visited once
- Adding linear terms incorrectly
5. Examine the following buggy code snippet for Sudoku validation using bitmasking:
def isValidSudoku(board):
rows = [0] * 9
cols = [0] * 9
boxes = [0] * 9
for i in range(9):
for j in range(9):
if board[i][j] == '.':
continue
val = ord(board[i][j]) - ord('1')
mask = 1 << val
box_index = i // 3 + (j // 3) * 3
if (rows[i] & mask) or (cols[j] & mask) or (boxes[box_index] & mask):
return false
rows[i] |= mask
cols[j] |= mask
boxes[box_index] |= mask
return truemedium
Solution
Step 1: Analyze box_index calculation
The code uses box_index = i // 3 + (j // 3) * 3, which swaps row and column grouping.Step 2: Correct formula for box_index
The correct formula is (i // 3) * 3 + (j // 3) to map 3x3 boxes properly.Final Answer:
Option D -> Option DQuick Check:
Incorrect box_index causes missed duplicates in boxes [OK]
Hint: Box index formula must map 3x3 boxes correctly [OK]
Common Mistakes:
- Swapping row and column in box index
- Misusing bitmask shifts
- Including '.' in checks