Rotate Matrix 90° Clockwise (leetcode 48)

48. Rotate Image

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.

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]]

Corrected approach: transpose the matrix (swap a[i][j] with a[j][i] for j>i) then reverse each row.

public class Main {
    public static void main(String[] args) {

        int[][] a = {{1,2,3},{4,5,6},{7,8,9}};
        int n = a.length;

        // Transpose
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int t = a[i][j];
                a[i][j] = a[j][i];
                a[j][i] = t;
            }
        }

        // Reverse each row
        for (int i = 0; i < n; i++) {
            int s = 0, e = n - 1;
            while (s < e) {
                int t = a[i][s];
                a[i][s] = a[i][e];
                a[i][e] = t;
                s++; e--;
            }
        }

    }
}

class Solution:
    def rotate(self, matrix):
        n = len(matrix)
        for i in range(n):
            for j in range(i + 1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        for i in range(n):
            matrix[i].reverse()

Type	Value
Time	O(n²)
Space	O(1)

• Dry run (3x3):
  • After transpose: [[1,4,7],[2,5,8],[3,6,9]]
  • Reverse rows: [7,4,1]; [8,5,2]; [9,6,3]
  • Output :
    7 4 1
    8 5 2
    9 6 3

Spiral Matrix 1 (leetcode 54)

54. Spiral Matrix

Given an m x n matrix, return all elements of the matrix in spiral order.

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

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

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();

        int top = 0;
        int bottom = matrix.length - 1;

        int left = 0;
        int right = matrix[0].length - 1;

        while(top <= bottom && left <= right){
            for(int i = left; i <= right; i++){
                res.add(matrix[top][i]);
            }

            top++;

            for(int i = top; i <= bottom; i++){
                res.add(matrix[i][right]);
            }

            right--;

            if(top <= bottom){
                for(int i = right; i >= left; i--){
                    res.add(matrix[bottom][i]);
                }
                bottom--;
            }

            if(left <= right){
                for(int i = bottom; i >= top; i--){
                    res.add(matrix[i][left]);
                }

                left++;
            }
        }

        return res;
    }
}

class Solution:
    def spiralOrder(self, matrix):
        res = []
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1
        
        while top <= bottom and left <= right:
            for i in range(left, right + 1):
                res.append(matrix[top][i])
            top += 1
            
            for i in range(top, bottom + 1):
                res.append(matrix[i][right])
            right -= 1
            
            if top <= bottom:
                for i in range(right, left - 1, -1):
                    res.append(matrix[bottom][i])
                bottom -= 1
                
            if left <= right:
                for i in range(bottom, top - 1, -1):
                    res.append(matrix[i][left])
                left += 1
                
        return res

Type	Value
Time	O(m × n)
Space	O(1)

• Dry run (3x3 matrix):
  • Traverse left to right (top row): [1,2,3], top becomes 1
  • Traverse top to bottom (right col): [6,9], right becomes 1
  • Traverse right to left (bottom row): [8,7], bottom becomes 1
  • Traverse bottom to top (left col): [4], left becomes 1
  • Traverse left to right (inner row): [5], top becomes 2 -> loop ends

---

Special Positions in a Binary Matrix(leetcode 1582)

1582. Special Positions in a Binary Matrix

Given an m x n binary matrix mat, return the number of special positions in mat.

A position (i, j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed).

Example 1:

Input: mat = [[1,0,0],[0,0,1],[1,0,0]]
Output: 1
Explanation: (1, 2) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0.

Example 2:

Input: mat = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
Explanation: (0, 0), (1, 1) and (2, 2) are special positions.

class Solution {
    public int numSpecial(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
       
        int[] r = new int[m];
        int[] c = new int[n];
       
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) {
                    r[i]++;
                    c[j]++;
                }
            }
        }
       
        int cp = 0;
       
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1 && r[i] == 1 && c[j] == 1) {
                    cp++;
                }
            }
        }
       
        return cp;
    }
}

class Solution:
    def numSpecial(self, mat):
        m, n = len(mat), len(mat[0])
        r = [0] * m
        c = [0] * n
        
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    r[i] += 1
                    c[j] += 1
                    
        cp = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1 and r[i] == 1 and c[j] == 1:
                    cp += 1
        return cp

Type	Value
Time	O(m × n)
Space	O(m + n)

• Dry run (mat = [[1,0,0],[0,0,1],[1,0,0]]):
  • Initial counts:
    • row sums (r): [1, 1, 1]
    • col sums (c): [2, 0, 1]
  • Iterate matrix:
    • mat[0][0] == 1 but c[0] == 2 -> not special
    • mat[1][2] == 1 and r[1] == 1 and c[2] == 1 -> special, count = 1
    • mat[2][0] == 1 but c[0] == 2 -> not special
  • Final count = 1

---

Set Matrix Zeros (Leetcode 73)

73. Set Matrix Zeroes

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

You must do it in place.

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2:

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

class Solution {
    public void setZeroes(int[][] matrix) {

        int m = matrix.length;
        int n = matrix[0].length;

        boolean firstRow = false;
        boolean firstCol = false;

        // check first column
        for(int i = 0; i < m; i++){
            if(matrix[i][0] == 0) firstCol = true;
        }

        // check first row
        for(int j = 0; j < n; j++){
            if(matrix[0][j] == 0) firstRow = true;
        }

        // mark rows and columns
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // fill zeros
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(matrix[i][0] == 0 || matrix[0][j] == 0){
                    matrix[i][j] = 0;
                }
            }
        }

        if(firstRow){
            for(int j = 0; j < n; j++) matrix[0][j] = 0;
        }

        if(firstCol){
            for(int i = 0; i < m; i++) matrix[i][0] = 0;
        }
    }
}

class Solution:
    def setZeroes(self, matrix):
        m, n = len(matrix), len(matrix[0])
        first_row = any(matrix[0][j] == 0 for j in range(n))
        first_col = any(matrix[i][0] == 0 for i in range(m))
        
        for i in range(1, m):
            for j in range(1, 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:
            for j in range(n):
                matrix[0][j] = 0
                
        if first_col:
            for i in range(m):
                matrix[i][0] = 0

Type	Value
Time	O(m × n)
Space	O(1)

• Approach: Use first row and first column as markers. First, check if the first row/column themselves contain zeros. Then, iterate through the rest of the matrix, marking zeros in the first row/column. Finally, fill zeros based on markers and handle first row/column.
• Dry run (matrix = [[1,1,1],[1,0,1],[1,1,1]]):
  • firstRow=false, firstCol=false
  • matrix[1][1]=0 → mark matrix[1][0]=0, matrix[0][1]=0
  • Fill: row 1 all zeros (matrix[1][0]=0), col 1 all zeros (matrix[0][1]=0)
  • Result: [[1,0,1],[0,0,0],[1,0,1]]

---

Flipping an Image (LeetCode 832)

832. Flipping an Image

Given an n x n binary matrix image, flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed.

• For example, flipping [1,1,0] horizontally results in [0,1,1].

To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0.

• For example, inverting [0,1,1] results in [1,0,0].

Example 1:

Input: image = [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

Example 2:

Input: image = [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

class Solution {
    public int[][] flipAndInvertImage(int[][] image) {

        int m = image.length;
        int n = image[0].length;

        for(int i = 0; i < m; i++){
            int s = 0, e = n - 1;

            while(s <= e){

                int temp = image[i][s] ^ 1;
                image[i][s] = image[i][e] ^ 1;
                image[i][e] = temp;

                s++;
                e--;
            }
        }

        return image;
    }
}

class Solution:
    def flipAndInvertImage(self, image):
        m, n = len(image), len(image[0])
        for i in range(m):
            s, e = 0, n - 1
            while s <= e:
                temp = image[i][s] ^ 1
                image[i][s] = image[i][e] ^ 1
                image[i][e] = temp
                s += 1
                e -= 1
        return image

Type	Value
Time	O(n²)
Space	O(1)

• Approach: For each row, use two pointers from both ends. Swap and invert simultaneously using XOR with 1.
• Dry run (image = [[1,1,0],[1,0,1],[0,0,0]]):
  • Row 0: swap+invert (0,2): [1,1,0] → s=0,e=2: temp=1^1=0, img[0]=0^1=1, img[2]=0 → [1,1,0]. s=1,e=1: temp=1^1=0, img[1]=1^1=0, img[1]=0 → [1,0,0]
  • Row 1: s=0,e=2: temp=1^1=0, img[0]=1^1=0, img[2]=0 → [0,0,0]. s=1,e=1: 0^1=1 → [0,1,0]
  • Row 2: s=0,e=2: temp=0^1=1, img[0]=0^1=1, img[2]=1 → [1,0,1]. s=1,e=1: 0^1=1 → [1,1,1]
  • Result: [[1,0,0],[0,1,0],[1,1,1]]

---

Number of Islands (LeetCode 200)

200. Number of Islands

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3

class Solution {

    public int numIslands(char[][] grid) {

        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
       
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
           
                if(grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
    private void dfs(char[][] grid, int i, int j) {
        int m = grid.length;
        int n = grid[0].length;
       
        if(i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == '0')
            return;
           
        grid[i][j] = '0';
        dfs(grid, i+1, j);
       
        dfs(grid, i-1, j);
        dfs(grid, i, j+1);
        dfs(grid, i, j-1);
    }
}

class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0
            
        m, n = len(grid), len(grid[0])
        count = 0
        
        def dfs(i, j):
            if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] == '0':
                return
            grid[i][j] = '0'
            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)
            
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1
                    dfs(i, j)
                    
        return count

Type	Value
Time	O(m × n)
Space	O(m × n)

• Approach: Iterate through the grid. When a '1' is found, increment count and DFS to mark all connected '1's as '0' (visited).
• Dry run (grid = [["1","1","0"],["0","1","0"],["0","0","1"]]):
  • (0,0)='1' → count=1, DFS marks (0,0),(0,1),(1,1) as '0'
  • (2,2)='1' → count=2, DFS marks (2,2) as '0'
  • Result: 2

---

Determine Whether Matrix Can Be Obtained By Rotation (LeetCode 1886)

1886. Determine Whether Matrix Can Be Obtained By Rotation

Given two n x n binary matrices mat and target, return true if it is possible to make mat equal to target by rotating mat in 90-degree increments, or false otherwise.

Example 1: Input: mat = [[0,1],[1,0]], target = [[1,0],[0,1]] Output: true Explanation: We can rotate mat 90 degrees clockwise to make mat equal target. Example 2:

class Solution {
    public boolean findRotation(int[][] mat, int[][] target) {
        for (int i = 0; i < 4; i++) {
            if (isEqual(mat, target)) return true;
            rotate(mat);
        }
        return false;
    }

    private boolean isEqual(int[][] a, int[][] b) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (a[i][j] != b[i][j]) return false;
            }
        }
        return true;
    }

    private void rotate(int[][] mat) {
        int n = mat.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = mat[i][j];
                mat[i][j] = mat[j][i];
                mat[j][i] = temp;
            }
        }

        for (int i = 0; i < n; i++) {
            int left = 0, right = n - 1;
            while (left < right) {
                int temp = mat[i][left];
                mat[i][left] = mat[i][right];
                mat[i][right] = temp;
                left++;
                right--;
            }
        }
    }
}

class Solution:
    def findRotation(self, mat, target):
        def rotate(m):
            n = len(m)
            for i in range(n):
                for j in range(i, n):
                    m[i][j], m[j][i] = m[j][i], m[i][j]
            for i in range(n):
                m[i].reverse()
                
        for _ in range(4):
            if mat == target:
                return True
            rotate(mat)
        return False

Type	Value
Time	O(n²)
Space	O(1)

• Approach: Check equality with target, then rotate mat 90 degrees clockwise up to 4 times. If it matches, return true.
• Dry run (mat=[[0,1],[1,0]], target=[[1,0],[0,1]]):
  • i=0: not equal. Rotate: transpose -> [[0,1],[1,0]], reverse rows -> [[1,0],[0,1]].
  • i=1: equal! return true.

---

Matrix Multiplication (GeeksforGeeks)

GeeksforGeeks

Given two n x n matrices A and B, compute their product matrix C.

Example:
Input: A = [[1,2],[3,4]], B = [[5,6],[7,8]]
Output: [[19,22],[43,50]]

class Solution {
    public static int[][] multiply(int A[][], int B[][]) {
        int n = A.length;
        int[][] C = new int[n][n];

        for (int i = 0; i < n; i++) {          
            for (int k = 0; k < n; k++) { 
                for (int j = 0; j < n; j++) {    
                    C[i][j] += A[i][k] * B[k][j];
                }
            }
        }

        return C;
    }
}

class Solution:
    def multiply(self, A, B):
        n = len(A)
        C = [[0] * n for _ in range(n)]
        
        for i in range(n):
            for k in range(n):
                for j in range(n):
                    C[i][j] += A[i][k] * B[k][j]
        return C

Type	Value
Time	O(n³)
Space	O(n²)

• Approach: Standard matrix multiplication. For each cell (i, j) in C, compute the dot product of the i-th row of A and the j-th column of B.
• Dry run (A=[[1,2],[3,4]], B=[[5,6],[7,8]]):
  • C[0][0] = 15 + 27 = 19
  • C[0][1] = 16 + 28 = 22
  • C[1][0] = 35 + 47 = 43
  • C[1][1] = 36 + 48 = 50
  • Returns C.

---