Rotate Image (90° Clockwise)

📋

Problem

Imagine you are developing a photo editing app and need to rotate images efficiently in-place without using extra memory.

Given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise) in-place. You must rotate the matrix without allocating another 2D matrix.

1 ≤ n ≤ 1000matrix[i][j] is an integerRotation must be done in-place with O(1) extra space

Edge cases: 1x1 matrix → same matrix after rotation2x2 matrix → simple swap of corners and edgesMatrix with all identical elements → output same as input

</>

IDE

def rotate(matrix: list[list[int]]) -> None:public void rotate(int[][] matrix)void rotate(vector<vector<int>>& matrix)function rotate(matrix)

def rotate(matrix):
    # Write your solution here
    pass

class Solution {
    public void rotate(int[][] matrix) {
        // Write your solution here
    }
}

#include <vector>
using namespace std;

void rotate(vector<vector<int>>& matrix) {
    // Write your solution here
}

function rotate(matrix) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[3,6,9],[2,5,8],[1,4,7]]Rotated by 90 degrees counter-clockwise instead of clockwise.✅ After transpose, reverse each row (not column) to rotate clockwise.

Wrong: [[7,8,9],[4,5,6],[1,2,3]]Only reversed rows without transposing first.✅ First transpose the matrix, then reverse each row.

Wrong: [[1,4,7],[2,5,8],[3,6,9]]Only transposed matrix without reversing rows.✅ Reverse each row after transpose to complete rotation.

Wrong: [[7,4,1],[8,5,2],[9,6,3]] but with some elements overwrittenIncorrect in-place swaps causing data overwrite.✅ Use temporary variable or four-way swaps carefully to avoid overwriting.

Wrong: [[2,0],[3,1]]Reversed columns instead of rows after transpose.✅ Reverse rows, not columns, after transpose.

✓

Test Cases

Focus on handling smallest and boundary matrix sizes correctly.

Review your transpose and reverse logic carefully to avoid common pitfalls.

Ensure your solution is efficient and uses no extra space.

t1_01basic

Input{"matrix":[[9,8,7],[6,5,4],[3,2,1]]}

Expectednull

⏱ Performance - must finish in 2000ms

After rotation, the first row becomes the last column, the second row becomes the middle column, and so on.

💡 Think about transposing the matrix first.

💡 After transposing, reverse each row to achieve the rotation.

💡 Use dp[i][j] = matrix[j][i] for transpose, then reverse rows in-place.

Why it failed: Output incorrect - likely forgot to reverse rows after transpose. Fix by reversing each row in-place after transposing.

✓ Correct rotation by transpose and reverse rows.

t1_02basic

Input{"matrix":[[16,12,14,15],[7,6,3,13],[10,8,4,2],[11,9,1,5]]}

Expectednull

⏱ Performance - must finish in 2000ms

4x4 matrix rotated 90 degrees clockwise by transpose and reversing each row.

💡 Transpose swaps matrix[i][j] with matrix[j][i].

💡 After transpose, reverse each row to complete rotation.

💡 Check indices carefully during transpose and reversal.

Why it failed: Incorrect output - probably did not transpose correctly or reversed columns instead of rows. Fix by swapping matrix[i][j] with matrix[j][i] for i<j and then reverse each row.

✓ Rotation logic correctly applied for 4x4 matrix.

t2_01edge

Input{"matrix":[[1]]}

Expectednull

⏱ Performance - must finish in 2000ms

1x1 matrix remains the same after rotation.

💡 Consider the smallest possible matrix size.

💡 Rotation of a single element matrix should not change it.

💡 Ensure your code handles n=1 without errors or unnecessary swaps.

Why it failed: Fails on 1x1 matrix - likely index errors or unnecessary swaps. Fix by handling n=1 case or ensuring loops handle single element correctly.

✓ Correctly handles 1x1 matrix without changes.

t2_02edge

Input{"matrix":[[4,3],[2,1]]}

Expectednull

⏱ Performance - must finish in 2000ms

2x2 matrix rotated 90 degrees clockwise swaps corners and edges accordingly.

💡 Test your logic on the smallest even dimension matrix.

💡 Check that your transpose swaps only above diagonal elements.

💡 Reverse each row after transpose to complete rotation.

Why it failed: Incorrect output for 2x2 - possibly swapped elements incorrectly or reversed columns instead of rows. Fix by transposing correctly and reversing rows.

✓ Correct rotation for 2x2 matrix.

t2_03edge

Input{"matrix":[[7,7,7],[7,7,7],[7,7,7]]}

Expectednull

⏱ Performance - must finish in 2000ms

Matrix with all identical elements remains the same after rotation.

💡 Check if your code unnecessarily modifies identical elements.

💡 Rotation should preserve identical values in new positions.

💡 Verify in-place operations do not corrupt data.

Why it failed: Output differs from input for identical elements - likely overwriting values incorrectly. Fix by using proper in-place swaps without data loss.

✓ Correctly rotates matrix with identical elements.

t3_01corner

Input{"matrix":[[9,8,7],[6,5,4],[3,2,1]]}

Expectednull

⏱ Performance - must finish in 2000ms

Greedy approach trap: rotating layer by layer incorrectly without proper swaps.

💡 Beware of rotating elements one by one without proper indexing.

💡 Use layer-by-layer four-way swaps carefully to avoid overwriting.

💡 Implement rotation by swapping four elements at a time per layer.

Why it failed: Incorrect output due to partial or incorrect layer rotation swaps. Fix by performing four-way swaps for each layer and position.

✓ Correctly handles layer-by-layer rotation with four-way swaps.

t3_02corner

Input{"matrix":[[3,2],[1,0]]}

Expectednull

⏱ Performance - must finish in 2000ms

Confusion between transpose and reverse steps causes wrong output.

💡 Check if you reversed columns instead of rows after transpose.

💡 Transpose swaps matrix[i][j] with matrix[j][i] for i<j only.

💡 Reverse each row, not column, after transpose.

Why it failed: Output incorrect because reversed columns instead of rows after transpose. Fix by reversing rows after transpose, not columns.

✓ Correctly applies transpose and row reversal.

t3_03corner

Input{"matrix":[[16,15,14,13],[12,11,10,9],[8,7,6,5],[4,3,2,1]]}

Expectednull

⏱ Performance - must finish in 2000ms

Off-by-one error in loops causes incorrect rotation for even-sized matrix.

💡 Check loop boundaries carefully when transposing.

💡 Transpose only elements where j > i to avoid double swapping.

💡 Reverse each row fully after transpose.

Why it failed: Incorrect output due to off-by-one errors in transpose loops. Fix by ensuring inner loop starts at j = i + 1.

✓ Correctly handles loop boundaries for transpose and reversal.

t4_01performance

Input{"_description":"n=1000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Large 1000x1000 matrix rotation must complete within 2 seconds using O(n^2) time and O(1) space.

💡 Algorithm must be O(n^2) time complexity.

💡 Avoid extra space; rotate in-place by transpose and reverse rows.

💡 Nested loops must be efficient and avoid redundant operations.

Why it failed: TLE due to using O(n^3) or extra space approach. Fix by implementing in-place transpose and row reversal with O(n^2) complexity.

✓ Efficient O(n^2) in-place rotation confirmed.

Practice

1. Consider the following Python function that counts negative numbers in a sorted matrix. What is the returned value when the input matrix is [[3, 1, -1], [2, 0, -2], [1, -1, -3]]?

def countNegatives(grid):
    m, n = len(grid), len(grid[0])
    count = 0
    row, col = 0, n - 1
    while row < m and col >= 0:
        if grid[row][col] < 0:
            count += m - row
            col -= 1
        else:
            row += 1
    return count

easy

A. 6

B. 5

C. 7

D. 8

Solution

1. Step 1: Trace first iteration

   Start at (0,2): grid[0][2] = -1 < 0, count += 3 - 0 = 3, col = 1

2. Step 2: Trace subsequent iterations

   At (0,1): 1 >= 0, row = 1; At (1,1): 0 >= 0, row = 2; At (2,1): -1 < 0, count += 3 - 2 = 1, col = 0; At (2,0): 1 >= 0, row = 3 (end)

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Counted negatives: 3 + 1 + 2 (from last col) = 6 [OK]

Hint: Count increments by rows below current on negative found [OK]

Common Mistakes:

• Off-by-one in counting rows below
• Incrementing row or col incorrectly
• Misreading matrix indices

2. Consider the following Python code 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 = [max(matrix[i][j] for i in range(m)) for j in range(n)]
    return [matrix[i][j] for i in range(m) for j in range(n) if matrix[i][j] == row_mins[i] == col_maxs[j]]

mat = [[3,7,8],[9,11,13],[15,16,17]]
print(luckyNumbers(mat))

What is the output of this code?

easy

A. [15]

B. [3, 11, 17]

C. [8, 13, 17]

D. [7, 11, 16]

Solution

1. Step 1: Compute row minimums

   Row 0 min = 3, Row 1 min = 9, Row 2 min = 15.

2. Step 2: Compute column maximums

   Col 0 max = max(3,9,15) = 15, Col 1 max = max(7,11,16) = 16, Col 2 max = max(8,13,17) = 17.

3. Step 3: Find elements equal to both row min and column max

   Check each element: - (2,0) = 15 equals row 2 min and col 0 max -> lucky number. No other elements satisfy both conditions.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Only 15 matches both conditions -> output [15] [OK]

Hint: Check row mins and col maxs carefully [OK]

Common Mistakes:

• Confusing min and max
• Off-by-one indexing
• Returning all row mins or col maxs

3. You are given a 2D matrix and asked to find the maximum sum of a pattern shaped like an hourglass (3 elements on top row, 1 in the middle, 3 on bottom row). Which approach guarantees an optimal solution with O(n*m) time complexity and O(1) extra space?

easy

A. Use a greedy approach to pick the largest elements in each row independently.

B. Use a brute force approach by checking every possible 3x3 submatrix sum.

C. Use dynamic programming to store maximum sums of smaller subproblems and combine them.

D. Use a sliding window technique that updates the hourglass sum by adding and removing only the changed elements when moving right.

Solution

1. Step 1: Understand the hourglass pattern

   The hourglass consists of 7 fixed positions in a 3x3 block, not the entire 3x3 matrix.

2. Step 2: Recognize the sliding window optimization

   Sliding window updates the sum by removing left column elements and adding right column elements, achieving O(n*m) time and O(1) space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sliding window updates sums efficiently without recomputing full sums [OK]

Hint: Sliding window updates sums incrementally [OK]

Common Mistakes:

• Confusing hourglass with full 3x3 submatrix sum
• Thinking DP is needed
• Assuming greedy works for max sum pattern

4. Consider the following Python function that returns the spiral order of a matrix. What is the output of spiralOrder([[1,2],[3,4]])?

easy

A. [1, 2, 3, 4]

B. [1, 2, 4, 3]

C. [1, 3, 4, 2]

D. [1, 4, 3, 2]

Solution

1. Step 1: Trace first iteration

   Top=0, Bottom=1, Left=0, Right=1. Append top row: [1, 2]. Increment top to 1.

2. 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.

3. Final Answer:

   Option B -> Option B

4. Quick 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

5. The following code attempts to return the spiral order of a matrix. Which line contains a subtle bug that can cause repeated elements or index errors?

medium

A. Line where bottom row is traversed without checking if top <= bottom

B. Line where right is decremented after traversing the right column

C. Line where left column is traversed with boundary check

D. Line where top is incremented after traversing the top row

Solution

1. Step 1: Identify missing boundary check

   The code traverses the bottom row without verifying if top <= bottom, which can cause duplicates or index errors when boundaries cross.

2. Step 2: Confirm other lines are correct

   Top increment, right decrement, and left column traversal have proper boundary checks or are logically correct.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing boundary check before bottom row traversal causes subtle bugs [OK]

Hint: Check boundary conditions before each traversal [OK]

Common Mistakes:

• Forgetting boundary checks before bottom or left traversal
• Incorrectly updating boundaries causing infinite loops
• Misplaced increments/decrements