DSA Series: Matrix (Blind 75, Java)

Overview

• Pattern cheat-sheet
• 1. Set Matrix Zeroes (Medium · LeetCode 73)
• 2. Spiral Matrix (Medium · LeetCode 54)
• 3. Rotate Image (Medium · LeetCode 48)
• 4. Word Search (Medium · LeetCode 79)

Part of the DSA Blind 75 series. Track your progress on the Interview Prep page.

Java 11+ solutions for 4 matrix problems, written for product / fintech interviews (Visa, Mastercard, NPCI, American Express, PayU). Every Java snippet in this file was compiled with javac and checked with assertions on the official examples, edge cases (1xN, Nx1, 1x1) and randomized cross-checks between approaches.

Pattern cheat-sheet

Indexing and traversal basics

• matrix[row][col], m = matrix.length (rows), n = matrix[0].length (columns). Always check for empty input (m == 0 || n == 0) if the constraints allow it.
• 4-direction moves: int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}} and a bounds check r >= 0 && r < m && c >= 0 && c < n.
• Spiral order uses right, down, left, up: dr = {0,1,0,-1}, dc = {1,0,-1,0}.

Useful transformations

Recurring techniques

1. Layer / boundary peeling (top, bottom, left, right): Spiral Matrix, Rotate Image. Guard the second half of each loop with top <= bottom and left <= right so single rows / columns are not visited twice.
2. In-place encoding to reach O(1) space: reuse the matrix itself as markers (first row/column in Set Matrix Zeroes) or temporary sentinel values ('#' in Word Search; encode old+new state in one int in Game of Life).
3. Backtracking on a grid: mark the cell, recurse into neighbours, unmark on return. Time is exponential in the path length; prune early.
4. Direction arrays + visited / sentinel to avoid copy-pasting four near-identical branches.
5. Pitfall: Java 2-D arrays are arrays of rows; swapping row references is O(1), and rows can have different lengths in general ("jagged") - the problems here guarantee rectangular.

Interview habits for matrix problems

• Ask: is it square or rectangular? Can I modify the input? Is extra space allowed? (Each answer can change the solution entirely.)
• Run your code mentally on a 1x1, 1xN, Nx1 and a 2x2 matrix.
• In payments context, matrices model things like transaction grids, time-slot x terminal availability tables, and routing hop graphs; the follow-up is often "the matrix is huge / sparse / stored on disk".

1. Set Matrix Zeroes (Medium · LeetCode 73)

Problem statement Given an m x n integer matrix, if an element is 0, set its entire row and column to 0. Do it in place.

• [[1,1,1],[1,0,1],[1,1,1]] -> [[1,0,1],[0,0,0],[1,0,1]]
• [[0,1,2,0],[3,4,5,2],[1,3,1,5]] -> [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
• Constraints: 1 <= m, n <= 200, values in the 32-bit int range. Follow-up: O(1) extra space.

How the interviewer asks / follow-ups

• Disguised: "A grid of terminals (rows) x time-slots (columns). If any terminal reports a fault in a slot, the whole terminal is disabled and the whole time-slot is blocked for the network. Update the availability grid in place." Or "blacklist all rows/columns that contain a flagged transaction".
• Follow-ups: (a) O(m+n) space then O(1) space; (b) why you cannot zero rows immediately (you would create new zeros that cascade); (c) use a sentinel instead of the first row/col - only valid if a value outside the domain exists; (d) matrix too big for memory -> process by streaming rows and keeping colHasZero bits plus a per-row flag; (e) sparse matrix stored as coordinates.
• Evaluating: do you avoid the cascade bug, can you get to O(1) space, and do you handle the first row / first column conflict correctly.

Approach 1: Brute force (copy) Copy the matrix; for every zero in the copy, zero its row and column in the original. Time O(mn(m+n)) worst case (each zero scans a row and column), space O(m*n).

Approach 2: Row and column marker arrays First pass: record row[i]/col[j] for each zero. Second pass: zero every cell whose row or column is flagged. Time O(m*n), space O(m+n).

Approach 3: Use first row / first column as markers (final) The first row and column serve as the marker arrays. Their own zero status would be overwritten, so first record it in two booleans. Then:

1. Scan inner cells [1..][1..]; when matrix[i][j] == 0 set matrix[i][0] = 0 and matrix[0][j] = 0.
2. Zero inner cells whose row marker or column marker is 0.
3. Finally zero the first row / first column if their saved flag says so.

Dry run on [[1,1,1],[1,0,1],[1,1,1]]: flags both false; step 1 marks matrix[1][0]=0 and matrix[0][1]=0 -> [[1,0,1],[0,0,1],[1,1,1]]; step 2 zeros inner cells in row 1 or column 1 -> [[1,0,1],[0,0,0],[1,0,1]]; step 3 does nothing.

Java code

public class SetZeroes {
    // Approach 1: copy of the matrix - O(m*n) time, O(m*n) space
    public static void setZeroesCopy(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] copy = new int[m][];
        for (int i = 0; i < m; i++) copy[i] = matrix[i].clone();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (copy[i][j] == 0) {
                    for (int k = 0; k < n; k++) matrix[i][k] = 0;
                    for (int k = 0; k < m; k++) matrix[k][j] = 0;
                }
    }

    // Approach 2: row / column marker arrays - O(m*n) time, O(m+n) space
    public static void setZeroesMarkers(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[] row = new boolean[m], col = new boolean[n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (matrix[i][j] == 0) { row[i] = true; col[j] = true; }
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (row[i] || col[j]) matrix[i][j] = 0;
    }

    // Approach 3: use first row / first column as markers - O(m*n) time, O(1) space
    public static void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean firstRowZero = false, firstColZero = false;
        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;

        for (int i = 1; i < m; i++)                 // record in first row/col
            for (int j = 1; j < n; j++)
                if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; }

        for (int i = 1; i < m; i++)                 // apply markers to the inner block
            for (int j = 1; j < n; j++)
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;

        if (firstRowZero) for (int j = 0; j < n; j++) matrix[0][j] = 0;   // markers' own row/col last
        if (firstColZero) for (int i = 0; i < m; i++) matrix[i][0] = 0;
    }
}

Complexity

Edge cases / pitfalls

• Zeroing eagerly cascades zeros across the whole matrix; always separate "detect" from "apply".
• Process the first row and column last; applying them before step 2 destroys the markers.
• 1 x n and m x 1 matrices (inner block is empty; still correct).
• Do not use a sentinel like -1/Integer.MIN_VALUE unless you can guarantee it is not an input value (here the full int range is allowed, so the first-row/col trick is safer).
• matrix[0][0] is shared by the first row marker and the first column marker - that is why two separate booleans are needed.

Pattern & related problems In-place marking / using the input as its own scratch space. Related: Game of Life (289), Rotate Image (48), Spiral Matrix (54), Valid Sudoku (36), First Missing Positive (41, same index-as-marker idea).

2. Spiral Matrix (Medium · LeetCode 54)

Problem statement Return all elements of an m x n matrix in clockwise spiral order starting from the top-left.

• [[1,2,3],[4,5,6],[7,8,9]] -> [1,2,3,6,9,8,7,4,5]
• [[1,2,3,4],[5,6,7,8],[9,10,11,12]] -> [1,2,3,4,8,12,11,10,9,5,6,7]
• Constraints: 1 <= m, n <= 10, -100 <= matrix[i][j] <= 100.

How the interviewer asks / follow-ups

• Disguised: "Print a statement/heat-map grid in a spiral from the outside in for a dashboard", "read a card-reader sensor matrix in spiral order", "traverse a seating/slot grid of terminals from the boundary inwards".
• Follow-ups: (a) Spiral Matrix II (59) - generate an n x n matrix filled 1..n^2 in a spiral; (b) counter-clockwise or start from the centre outward; (c) return the k-th element without building the list; (d) do it without extra visited array; (e) non-rectangular / extremely wide matrices.
• Evaluating: clean boundary management and no duplicated elements on single-row / single-column leftovers. It is mostly a careful-implementation test.

Approach 1: Direction vectors + visited Walk in the current direction; when the next cell is out of bounds or already visited, turn clockwise. Stop after m*n elements. Time O(mn), space O(mn) for visited.

Approach 2: Shrinking boundaries (final) Maintain top, bottom, left, right. Each loop iteration walks the ring: top row (left->right), right column (top->bottom), bottom row (right->left, only if top <= bottom), left column (bottom->top, only if left <= right), shrinking the corresponding bound after each side. Time O(m*n), extra space O(1) (excluding output). Dry run for the 3x3:

Result 1,2,3,6,9,8,7,4,5.

Java code

import java.util.*;

public class Spiral {
    // Approach 1: direction vectors + visited - O(m*n) time, O(m*n) space
    public static List<Integer> spiralVisited(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int m = matrix.length, n = matrix[0].length;
        boolean[][] seen = new boolean[m][n];
        int[] dr = {0, 1, 0, -1}, dc = {1, 0, -1, 0};   // right, down, left, up
        int r = 0, c = 0, d = 0;
        for (int k = 0; k < m * n; k++) {
            res.add(matrix[r][c]);
            seen[r][c] = true;
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || seen[nr][nc]) {   // turn clockwise
                d = (d + 1) % 4;
                nr = r + dr[d]; nc = c + dc[d];
            }
            r = nr; c = nc;
        }
        return res;
    }

    // Approach 2: shrinking boundaries - O(m*n) time, O(1) extra space (besides output)
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix.length == 0 || matrix[0].length == 0) return res;
        int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; j++) res.add(matrix[top][j]);         // left -> right
            top++;
            for (int i = top; i <= bottom; i++) res.add(matrix[i][right]);       // top -> bottom
            right--;
            if (top <= bottom) {                                                 // still a bottom row?
                for (int j = right; j >= left; j--) res.add(matrix[bottom][j]);  // right -> left
                bottom--;
            }
            if (left <= right) {                                                 // still a left column?
                for (int i = bottom; i >= top; i--) res.add(matrix[i][left]);    // bottom -> top
                left++;
            }
        }
        return res;
    }
}

Complexity

Edge cases / pitfalls

• Single row (1 x n) or single column (m x 1): without the top <= bottom / left <= right guards, the bottom row / left column would be emitted a second time.
• Odd dimensions leave a single middle row/column/cell.
• Empty matrix -> empty list.
• Loop condition while (top <= bottom && left <= right).
• Do not forget to update top++ right after the first row before the right-column loop starts at top.

Pattern & related problems Layer-by-layer boundary peeling. Related: Spiral Matrix II (59), Spiral Matrix III (885), Rotate Image (48), Diagonal Traverse (498), Zigzag Conversion (6), Print Matrix in Snake Order.

3. Rotate Image (Medium · LeetCode 48)

Problem statement Rotate an n x n matrix by 90 degrees clockwise, in place (do not allocate another 2-D matrix).

• [[1,2,3],[4,5,6],[7,8,9]] -> [[7,4,1],[8,5,2],[9,6,3]]
• [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] -> [[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.

How the interviewer asks / follow-ups

• Disguised: "A scanned cheque / ID-card / QR image is stored as an N x N pixel grid and was captured sideways - rotate it upright in place", "rotate a terminal-layout grid".
• Follow-ups: (a) counter-clockwise or 180 degrees; (b) non-square m x n (needs a new n x m array - cannot be done in place trivially); (c) rotate by k x 90 degrees (use k % 4); (d) explain the index mapping; (e) image is huge -> process in tiles / by layers.
• Evaluating: deriving (i,j) -> (j, n-1-i), the transpose + reverse trick, and in-place O(1) space.

Approach 1: Extra matrix Place matrix[i][j] at res[j][n-1-i]. Time O(n^2), space O(n^2). Not acceptable under the in-place constraint but a good starting point to derive the mapping.

Approach 2: Transpose, then reverse each row (final) Clockwise rotation = transpose (swap across main diagonal) followed by reversing each row. Dry run on the 3x3:

[1,2,3]      [1,4,7]      [7,4,1]
[4,5,6]  ->  [2,5,8]  ->  [8,5,2]
[7,8,9]      [3,6,9]      [9,6,3]
  original     transpose    reverse rows

Approach 3: Four-way cell rotation layer by layer For layer i and offset j, rotate the four cells top -> right -> bottom -> left -> top in a cycle using one temp variable. Visits each cell once; same complexity but a single pass.

Java code

public class RotateImage {
    // Approach 1: extra matrix - O(n^2) time, O(n^2) space. (i,j) -> (j, n-1-i)
    public static void rotateCopy(int[][] matrix) {
        int n = matrix.length;
        int[][] res = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                res[j][n - 1 - i] = matrix[i][j];
        for (int i = 0; i < n; i++) matrix[i] = res[i];     // LeetCode checks matrix contents
    }

    // Approach 2: transpose, then reverse every row - O(n^2) time, O(1) space
    public static void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {               // swap across the main diagonal
                int t = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = t;
            }
        for (int[] row : matrix)
            for (int l = 0, r = n - 1; l < r; l++, r--) {
                int t = row[l]; row[l] = row[r]; row[r] = t;
            }
    }

    // Approach 3: rotate four cells at a time, layer by layer - O(n^2) time, O(1) space
    public static void rotateLayers(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; i++) {
            for (int j = i; j < n - 1 - i; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];                 // left   -> top
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]; // bottom -> left
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]; // right  -> bottom
                matrix[j][n - 1 - i] = tmp;                          // top    -> right
            }
        }
    }

    // Follow-up: counter-clockwise = transpose, then reverse the order of the rows (up-down flip)
    public static void rotateCounterClockwise(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++)                         // transpose
            for (int j = i + 1; j < n; j++) {
                int t = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = t;
            }
        for (int l = 0, r = n - 1; l < r; l++, r--) {       // swap row references top <-> bottom
            int[] t = matrix[l]; matrix[l] = matrix[r]; matrix[r] = t;
        }
    }
}

Complexity

Edge cases / pitfalls

• Transpose loop must start at j = i + 1; looping the full square swaps each pair twice and restores the original.
• Four-way swap bounds: i from 0 to n/2 - 1, j from i to n - 2 - i; the centre cell of an odd n stays put.
• n = 1 -> no-op.
• Counter-clockwise is transpose + reverse the order of the rows (not the same as clockwise + reverse).
• Replacing row references (matrix[i] = res[i]) works for LeetCode (it checks the array contents) but is technically not "in place".

Pattern & related problems Matrix index transformations. Related: Spiral Matrix (54), Transpose Matrix (867), Flipping an Image (832), Rotate String (796), Determine Whether Matrix Can Be Obtained By Rotation (1886), Rotate Array (189, reverse trick).

4. Word Search (Medium · LeetCode 79)

Problem statement Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word is built from sequentially adjacent cells (horizontal or vertical neighbours); the same cell may not be used more than once.

• board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" -> true
• same board, word = "SEE" -> true
• same board, word = "ABCB" -> false
• Constraints: 1 <= m, n <= 6, 1 <= word.length <= 15, letters only. Follow-up: prune to make a large board / many words fast.

How the interviewer asks / follow-ups

• Disguised: "A fraud-detection grid of transaction categories - does a given suspicious category pattern appear along a path of adjacent cells?" or "Does a given sequence of terminal IDs form a connected walk on the topology grid without revisiting a node?"
• Follow-ups: (a) Word Search II (212) - many words -> build a Trie of all words and DFS the board once; (b) allow 8 directions; (c) return the path / coordinates; (d) pruning: letter-frequency check, search from the rarer end; (e) why backtracking needs "unmark" and why memoization of (r,c,k) does not directly apply (visited set is part of the state); (f) count the number of occurrences.
• Evaluating: correct backtracking with restore, bounds checking, early termination, and awareness of exponential worst case.

Approach 1: DFS with a visited array For each cell matching word[0], run DFS: mark the cell, try the 4 neighbours for word[k+1], unmark on return. Time O(mn * 3^L) (4 choices at the start, then at most 3 since you cannot go back), space O(mn + L).

Approach 2: In-place marking + pruning (final) Same DFS but temporarily overwrite the cell with '#' instead of a separate visited array (this also makes the mismatch check reject visited cells automatically) and restore it after. Optional pruning that helps on adversarial inputs such as a board full of 'a':

1. If word.length() > m*n -> false.
2. If the board has fewer copies of any letter than the word needs -> false.
3. If the first letter is more frequent on the board than the last, search the reversed word (fewer starting points / earlier failures).

Dry run for "ABCCED" on the sample board: start at (0,0)=A; B (0,1); C (0,2); next C is below at (1,2); E is below at (2,2); D is left at (2,1); all 6 letters matched -> true.

Java code

public class WordSearch {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    // Approach 1: DFS + separate visited array - O(m*n*3^L) time, O(m*n + L) space
    public static boolean existVisited(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (dfsV(board, word, 0, i, j, visited)) return true;
        return false;
    }
    private static boolean dfsV(char[][] b, String w, int k, int r, int c, boolean[][] vis) {
        if (k == w.length()) return true;
        if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || vis[r][c] || b[r][c] != w.charAt(k))
            return false;
        vis[r][c] = true;
        for (int[] d : DIRS)
            if (dfsV(b, w, k + 1, r + d[0], c + d[1], vis)) { vis[r][c] = false; return true; }
        vis[r][c] = false;                          // backtrack
        return false;
    }

    // Approach 2: in-place marking + pruning - same worst case O(m*n*3^L) time, O(L) space (recursion)
    public static boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        if (word.length() > m * n) return false;

        // Pruning 1: board must contain enough of every letter
        int[] freq = new int[128];
        for (char[] row : board) for (char ch : row) freq[ch]++;
        for (int i = 0; i < word.length(); i++)
            if (--freq[word.charAt(i)] < 0) return false;

        // Pruning 2: start from the rarer end (fewer starting cells / branches)
        int[] f = new int[128];
        for (char[] row : board) for (char ch : row) f[ch]++;
        if (f[word.charAt(0)] > f[word.charAt(word.length() - 1)])
            word = new StringBuilder(word).reverse().toString();

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (dfs(board, word, 0, i, j)) return true;
        return false;
    }
    private static boolean dfs(char[][] b, String w, int k, int r, int c) {
        if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] != w.charAt(k))
            return false;                           // also rejects the '#' visited marker
        if (k == w.length() - 1) return true;
        char saved = b[r][c];
        b[r][c] = '#';                              // mark visited (no word char is '#')
        boolean found = false;
        for (int[] d : DIRS) {
            if (dfs(b, w, k + 1, r + d[0], c + d[1])) { found = true; break; }
        }
        b[r][c] = saved;                            // restore on the way out
        return found;
    }
}

Complexity

Edge cases / pitfalls

• Must restore the cell (b[r][c] = saved) after exploring, even when returning true early in the in-place version (otherwise the caller's board is corrupted; the tests verify the board is unchanged).
• Check bounds before reading board[r][c].
• Base case: the word is fully matched on the last character - check k == word.length() - 1 after confirming the current cell matches.
• Word longer than m*n can never match.
• Single-cell board and single-character word.
• Reusing the same cell for consecutive letters ("AA" on [["A"]]) must return false.
• Do not cache by (r, c, k) alone - the path history (visited set) matters.

Pattern & related problems Grid backtracking / DFS with path-state. Related: Word Search II (212, Trie + backtracking), Number of Islands (200, DFS without unmark), Surrounded Regions (130), Path with Maximum Gold (1219), Unique Paths III (980), N-Queens (51), Combination Sum (39).