Rotate Image

LeetCode 48 | Difficulty: Medium

Medium

Problem Description

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

Example 2:

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

Constraints:

- `n == matrix.length == matrix[i].length`

- `1 <= n <= 20`

- `-1000 <= matrix[i][j] <= 1000`

Topics: Array, Math, Matrix

---

Approach

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

Matrix

Treat the matrix as a 2D grid. Common techniques: directional arrays (dx, dy) for movement, BFS/DFS for connected regions, in-place marking for visited cells, boundary traversal for spiral patterns.

When to use

Grid traversal, island problems, path finding, rotating/transforming matrices.

---

Solutions

Solution 1: C# (Best: 175 ms)

Metric	Value
Runtime	175 ms
Memory	N/A
Date	2017-11-05

Solution

public class Solution {
    public void Rotate(int[,] matrix) {
        ChangeSymmetry(matrix);
    Reverse(matrix);
}

private void ChangeSymmetry(int[,] matrix)
{
    for (int i = 0; i < matrix.GetLength(0); i++)
    {
        for (int j = i; j < matrix.GetLength(1); j++)
        {
            int temp = matrix[i,j];
            matrix[i,j] = matrix[j,i];
            matrix[j,i] = temp;
        }               
    }
}

private void Reverse(int[,] matrix)
{
    for (int i = 0; i < matrix.GetLength(0); i++)
    {
        int begin = 0, end = matrix.GetLength(0) - 1;
        while (begin < end)
        {
            int temp = matrix[i,begin];
            matrix[i,begin] = matrix[i,end];
            matrix[i,end] =  temp;
            begin++;
            end--;
        }
    }
}
}

📜 1 more C# submission(s)

Submission (2017-11-05) — 178 ms, N/A

public class Solution {
    public void Rotate(int[,] matrix) {
        if(matrix == null || matrix.GetLength(0) <= 1) return;
        ChangeSymmetry(matrix);
    Reverse(matrix);
}

private void ChangeSymmetry(int[,] matrix)
{
    for (int i = 0; i < matrix.GetLength(0); i++)
    {
        for (int j = i; j < matrix.GetLength(1); j++)
        {
            int temp = matrix[i,j];
            matrix[i,j] = matrix[j,i];
            matrix[j,i] = temp;
        }               
    }
}

private void Reverse(int[,] matrix)
{
    for (int i = 0; i < matrix.GetLength(0); i++)
    {
        int begin = 0, end = matrix.GetLength(0) - 1;
        while (begin < end)
        {
            int temp = matrix[i,begin];
            matrix[i,begin] = matrix[i,end];
            matrix[i,end] =  temp;
            begin++;
            end--;
        }
    }
}
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.