Rotate Image (90° Clockwise)

▶

Steps

setup

Initialize matrix size and start outer layer

Calculate the size of the matrix (n=3) and set the first layer index to 0 and last layer index to 2 (n-1).

💡 Knowing the layer boundaries is essential to control which elements to rotate in each iteration.

Line:

n = len(matrix)
for layer in range(n // 2):
    first = layer
    last = n - 1 - layer

💡 The outermost layer is from index 0 to 2, which covers the entire matrix border.

fill_cells

Start first element in outer layer

Set the current element index i to the first index of the layer (0). This is the first element in the top row of the current layer to rotate.

💡 We rotate elements one by one in the current layer, starting from the leftmost element.

Line:

for i in range(first, last):
    offset = i - first

💡 The offset helps calculate corresponding elements in other sides of the layer for swapping.

fill_cells

Save top element before swap

Store the top element at position (first, i) which is matrix[0][0] = 1, to a temporary variable 'top' before overwriting it.

💡 Saving the top element is necessary because it will be overwritten during the rotation but is needed later to complete the swap.

Line:

top = matrix[first][i]

💡 Temporarily storing the top element preserves its value for the final assignment in the four-way swap.

fill_cells

Move left element to top

Assign the left element at (last - offset, first) = matrix[2][0] = 7 to the top position (first, i) = matrix[0][0].

💡 This is the first step of the four-way swap, moving the left element into the top position.

Line:

matrix[first][i] = matrix[last - offset][first]

💡 Elements rotate clockwise by moving left to top, bottom to left, right to bottom, and top to right.

fill_cells

Move bottom element to left

Assign the bottom element at (last, last - offset) = matrix[2][2] = 9 to the left position (last - offset, first) = matrix[2][0].

💡 This continues the four-way swap by moving the bottom element into the left position.

Line:

matrix[last - offset][first] = matrix[last][last - offset]

💡 Each element moves one position clockwise in the layer.

fill_cells

Move right element to bottom

Assign the right element at (i, last) = matrix[0][2] = 3 to the bottom position (last, last - offset) = matrix[2][2].

💡 This step moves the right element down to the bottom position in the rotation.

Line:

matrix[last][last - offset] = matrix[i][last]

💡 The rotation continues by moving the right element to the bottom.

fill_cells

Move saved top element to right

Assign the saved top element 'top' = 1 to the right position (i, last) = matrix[0][2].

💡 This completes the four-way swap by placing the original top element into the right position.

Line:

matrix[i][last] = top

💡 The four-way swap rotates four elements clockwise in place without extra space.

fill_cells

Move to next element in outer layer (i=1)

Increment i to 1 to process the next element in the top row of the outer layer.

💡 We continue rotating the next set of four elements in the current layer.

Line:

for i in range(first, last):
    offset = i - first

💡 Each element in the layer's top row participates in a four-way swap.

fill_cells

Save top element at (0,1)

Save the top element matrix[0][1] = 2 to 'top' before overwriting it.

💡 Saving the top element is necessary for the four-way swap.

Line:

top = matrix[first][i]

💡 Temporary storage preserves the element for the final assignment.

fill_cells

Move left element to top (1,0) -> (0,1)

Move left element matrix[1][0] = 4 to top position matrix[0][1].

💡 This is the first move in the four-way swap for the second element.

Line:

matrix[first][i] = matrix[last - offset][first]

💡 Elements continue rotating clockwise in the layer.

fill_cells

Move bottom element to left (2,1) -> (1,0)

Move bottom element matrix[2][1] = 8 to left position matrix[1][0].

💡 Continuing the four-way swap, bottom moves to left.

Line:

matrix[last - offset][first] = matrix[last][last - offset]

💡 Each element moves one step clockwise.

fill_cells

Move right element to bottom (1,2) -> (2,1)

Move right element matrix[1][2] = 6 to bottom position matrix[2][1].

💡 Right element moves down to bottom in the rotation.

Line:

matrix[last][last - offset] = matrix[i][last]

💡 Rotation continues clockwise.

fill_cells

Move saved top element to right (0,1)

Assign saved top element 'top' = 2 to right position matrix[1][2].

💡 Completes the four-way swap for the second element.

Line:

matrix[i][last] = top

💡 Four-way swap completes the rotation of these elements.

setup

Outer layer rotation complete, move to inner layer

Increment layer to 1, which is the inner layer. Since n//2 = 1, no more layers to process, rotation is complete.

💡 For odd n, the center element remains unchanged, so no swaps needed in inner layer.

Line:

for layer in range(n // 2):

💡 Only one layer needed rotation for 3x3 matrix; center element stays the same.

reconstruct

Final rotated matrix

The matrix is fully rotated 90 degrees clockwise in place. The final matrix is [[7,4,1],[8,5,2],[9,6,3]].

💡 The in-place swaps have transformed the matrix without extra space.

Line:

print(matrix)

💡 The algorithm successfully rotated the matrix layer by layer.

def rotate(matrix):
    n = len(matrix)  # STEP 1
    for layer in range(n // 2):  # STEP 1,8,14
        first = layer  # STEP 1
        last = n - 1 - layer  # STEP 1
        for i in range(first, last):  # STEP 2,8
            offset = i - first  # STEP 2,8
            top = matrix[first][i]  # STEP 3,9
            matrix[first][i] = matrix[last - offset][first]  # STEP 4,10
            matrix[last - offset][first] = matrix[last][last - offset]  # STEP 5,11
            matrix[last][last - offset] = matrix[i][last]  # STEP 6,12
            matrix[i][last] = top  # STEP 7,13

if __name__ == '__main__':
    mat = [[1,2,3],[4,5,6],[7,8,9]]
    rotate(mat)  # STEP 1-14
    print(mat)  # STEP 15

📊

Rotate Image (90° Clockwise) - Watch the Algorithm Execute, Step by Step

Watching each swap and pointer movement helps you understand how the matrix rotates without extra space, revealing the symmetry and index calculations involved.

setup

first

0

1

last

2

fill_cells

i

0

1

last

2

record

i

0

1

last

2

move_left

i

0

1

last

2

move_bottom

i

0

1

last

2

move_right

i

0

1

last

2

move_top

i

0

1

last

2

fill_cells

first

0

i

1

last

2

record

first

0

i

1

last

2

move_left

first

0

i

1

last

2

move_bottom

first

0

i

1

last

2

move_right

first

0

i

1

last

2

move_top

first

0

i

1

last

2

prune

0

last

1

2

reconstruct

0

1

2

Result: [[7,4,1],[8,5,2],[9,6,3]]

Key Takeaways

✓ The rotation is done layer by layer, swapping four elements at a time in place.

This insight is hard to see from code alone because the index calculations and swaps are subtle and intertwined.

✓ Each element in the top row of a layer determines the four elements involved in the swap.

Visualizing the offset and layer boundaries clarifies how the algorithm covers the entire matrix without overlap.

✓ The center element in odd-sized matrices remains unchanged and does not require swapping.

This is a subtle optimization that prevents unnecessary operations and is easier to understand visually.

Practice

1. You need to fill an n x n matrix with numbers from 1 to n² in a pattern that starts at the top-left corner and proceeds in a clockwise spiral moving outward. Which approach guarantees filling all cells correctly without revisiting or skipping any cell?

easy

A. Greedy approach filling rows and columns independently without tracking boundaries

B. Dynamic programming to store partial sums and fill matrix based on subproblems

C. Directional simulation with boundary shrinking and cycling through directions

D. Sorting all numbers and placing them diagonally from top-left to bottom-right

Solution

1. Step 1: Understand the problem constraints

   The matrix must be filled in a spiral order, visiting each cell exactly once in a clockwise manner.

2. Step 2: Identify the approach that tracks boundaries and direction

   Directional simulation with boundary shrinking ensures that after filling one side, boundaries are updated to avoid revisiting cells, and directions cycle through right, down, left, and up correctly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Boundary shrinking prevents overwriting and ensures full coverage [OK]

Hint: Track boundaries and directions to avoid revisits [OK]

Common Mistakes:

• Assuming greedy row/column fills without boundary checks works
• Confusing DP with spiral traversal
• Ignoring direction cycling leads to incomplete fills

2. What is the time complexity of the optimal diagonal traversal algorithm for an m x n matrix, and why might some candidates incorrectly think it is higher?

medium

A. O((m + n)^2) because the number of diagonals is m + n - 1 and each diagonal is processed separately.

B. O(m * n * log(m + n)) because sorting diagonals is required.

C. O(m * n) because each element is visited exactly once along diagonals.

D. O(m * n * (m + n)) due to nested loops over diagonals and elements.

Solution

1. Step 1: Identify total elements visited

   The algorithm visits each of the m*n elements exactly once.

2. Step 2: Analyze loops over diagonals and elements

   There are m+n-1 diagonals, but total elements summed over all diagonals is m*n, so total work is O(m*n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Each element processed once -> linear in matrix size [OK]

Hint: Total elements visited once -> O(m*n) [OK]

Common Mistakes:

• Confusing number of diagonals with total elements processed

3. Consider the following buggy code for maximum hourglass sum using sliding window. Which line contains the subtle bug that can cause incorrect results when all matrix values are negative?

def max_hourglass_sum_sliding(matrix):
    n = len(matrix)
    m = len(matrix[0])
    max_sum = 0  # Bug here

    for i in range(n - 2):
        current_sum = (matrix[i][0] + matrix[i][1] + matrix[i][2] +
                       matrix[i+1][1] +
                       matrix[i+2][0] + matrix[i+2][1] + matrix[i+2][2])
        if current_sum > max_sum:
            max_sum = current_sum

        for j in range(1, m - 2):
            current_sum -= (matrix[i][j-1] + matrix[i+1][j] + matrix[i+2][j-1])
            current_sum += (matrix[i][j+2] + matrix[i+1][j+1] + matrix[i+2][j+2])
            if current_sum > max_sum:
                max_sum = current_sum
    return max_sum

medium

A. Line initializing max_sum to 0

B. Line computing current_sum for initial hourglass

C. Line subtracting left column elements in sliding window

D. Line adding right column elements in sliding window

Solution

1. Step 1: Understand initialization of max_sum

   Setting max_sum = 0 causes incorrect max when all values are negative, as max_sum never updates to negative sums.

2. Step 2: Confirm other lines are correct

   Current_sum calculation and sliding window updates are correct; bug is only in initialization.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Proper initialization must be -inf to handle negative values [OK]

Hint: Initialize max_sum to -inf to handle negative values [OK]

Common Mistakes:

• Initializing max_sum to 0
• Misindexing sliding window updates
• Forgetting to update max_sum after sliding

4. Consider the following buggy code snippet for generating an n x n spiral matrix. Which line contains the subtle bug that can cause incorrect output or infinite loops?

medium

A. Line updating 'right' boundary after downward fill

B. Line after filling top row: missing update of 'top' boundary

C. Line updating 'bottom' boundary after leftward fill

D. Line updating 'left' boundary after upward fill

Solution

1. Step 1: Identify boundary updates after each direction

   After filling the top row (direction 0), the 'top' boundary must be incremented to avoid overwriting.

2. Step 2: Locate missing update

   The code comment indicates the 'top' boundary update is missing, causing the loop to overwrite the same row repeatedly or cause infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing 'top += 1' causes repeated writes to top row [OK]

Hint: Each direction must update its boundary after filling [OK]

Common Mistakes:

• Forgetting to update one boundary after a direction
• Incorrectly updating boundaries leading to index errors
• Misordering direction cycling

5. Suppose the Game of Life rules are modified so that cells can be in one of three states: dead, alive, or dormant, and the next state depends on neighbors' states with more complex transitions. Which modification to the in-place encoding approach is necessary to correctly update the board?

hard

A. Use a larger integer encoding scheme with more states to represent current and next states simultaneously.

B. Switch to copying the entire board each iteration to avoid encoding complexity.

C. Update cells immediately without encoding since more states simplify neighbor counting.

D. Ignore dormant state neighbors during counting to reduce complexity.

Solution

1. Step 1: Understand the need for more states

   With three possible states and complex transitions, encoding must represent both current and next states simultaneously.

2. Step 2: Choose encoding approach

   Using a larger integer encoding scheme (e.g., 6 or more states) allows in-place updates without losing original state info.

3. Step 3: Reject naive approaches

   Copying the board increases space; immediate updates corrupt neighbor info; ignoring dormant neighbors breaks rules.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   More states require richer encoding to preserve info [OK]

Hint: More states require more encoding bits, not naive copying [OK]

Common Mistakes:

• Switching to copying board wastes space
• Immediate updates corrupt neighbor counts
• Ignoring certain neighbors breaks rules