Matrix Templates (Spiral, Search, Rotate, Zeroes)

Spiral Matrix (LeetCode 54)

Layer-by-layer simulation using four boundaries: top, bottom, left, and right.

List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> res = new ArrayList<>();
    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 1;

    while (top <= bottom && left <= right) {
        // Left to Right
        for (int i = left; i <= right; i++)      res.add(matrix[top][i]);
        top++;
        
        // Top to Bottom
        for (int i = top; i <= bottom; i++)      res.add(matrix[i][right]);
        right--;
        
        // Right to Left (if still valid)
        if (top <= bottom) {
            for (int i = right; i >= left; i--)  res.add(matrix[bottom][i]);
            bottom--;
        }
        
        // Bottom to Top (if still valid)
        if (left <= right) {
            for (int i = bottom; i >= top; i--)  res.add(matrix[i][left]);
            left++;
        }
    }
    return res;
}

Spiral Matrix II (LeetCode 59): Generates an n×n matrix filled in spiral order. Use the same boundary logic.

Search a 2D Matrix (LeetCode 74)

When rows and columns are strictly sorted, the entire matrix can be treated as a single sorted array for Binary Search:

boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    int lo = 0, hi = m * n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        // Map 1D index back to 2D
        int val = matrix[mid / n][mid % n];
        if (val == target) return true;
        if (val < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}

Search a 2D Matrix II (LeetCode 240): Rows and columns are sorted independently. Start from the top-right corner to eliminate possibilities:

boolean searchMatrixII(int[][] matrix, int target) {
    int r = 0, c = matrix[0].length - 1;
    while (r < matrix.length && c >= 0) {
        if (matrix[r][c] == target) return true;
        if (matrix[r][c] > target) c--;   // Current column elements are too big
        else r++;                         // Current row elements are too small
    }
    return false;
}

Complexity: Time O(m+n).

Rotate Image (LeetCode 48)

Rotate an n×n matrix 90 degrees in-place: Transpose the matrix then flip horizontally.

void rotate(int[][] matrix) {
    int n = matrix.length;
    // 1. Transpose (swap matrix[i][j] with matrix[j][i])
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            int t = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = t;
        }
    // 2. Flip each row horizontally
    for (int i = 0; i < n; i++) {
        int lo = 0, hi = n - 1;
        while (lo < hi) {
            int t = matrix[i][lo];
            matrix[i][lo++] = matrix[i][hi];
            matrix[i][hi--] = t;
        }
    }
}

Set Matrix Zeroes (LeetCode 73)

Use the first row and column as trackers to avoid extra O(mn) space:

void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean firstRowZero = false, firstColZero = false;

    // Check if first row/col originally contain zeros
    for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRowZero = true;
    for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstColZero = true;

    // Use first row/col as markers for the rest of the matrix
    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; 
            }

    // Iterate through the matrix and set zeros based on markers
    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;

    // Finally, zero out the first row and column if needed
    if (firstRowZero) Arrays.fill(matrix[0], 0);
    if (firstColZero) for (int i = 0; i < m; i++) matrix[i][0] = 0;
}

Complexity: Space O(1), Time O(mn).