Matrix
Data Structure

A matrix is a two-dimensional array consisting of rows (horizontal) and columns (vertical). Each element is accessed by an index pair (row, column) — like an XY coordinate where X = row number, Y = column number.

For a matrix with 4 rows and 6 columns: indices range from (0,0) to (3,5). The element at row 2, column 3 is accessed as matrix[2][3].

Worth understanding this deeply — index manipulation in 2D works exactly like 1D arrays, except you now track two coordinates instead of one.

Standard matrix traversal uses nested loops:

for (int i = 0; i < R; i++)      // rows
  for (int j = 0; j < C; j++)    // columns
    // operation on matrix[i][j]

Time complexity: O(R × C) — or O(M × N). If the matrix is square (N × N), this simplifies to O(N²).

Part 1 focused on techniques 2 and 3. BFS/DFS on matrices is covered in Part 2.

If your brute-force is O(N³) or O(N²), ask yourself: can extra space reduce it? This is the single most common optimization interviewers probe for. An approach with O(N) time + O(N) space is strictly better than O(N²) time + O(1) space. Interviewers will often push you: "Can you do better?" — reaching for an auxiliary array is your first fallback.

Interviewers are "obsessed" with BFS and DFS on matrices. If you're given a matrix problem in an interview, chances are high they'll test your BFS/DFS skills. Make sure you've revised the BFS template (queue-based) and DFS (recursion-based) before any interview.

Even if you've seen the exact problem before, pretend to think through it. If the interviewer senses you already know the answer, they'll skip to a harder problem you might not know. Take a moment, say "Let me think about this," then walk through the approach.

Standard expectation: solve 2 problems in 1 hour. Don't panic if one takes longer. But be aware: competition is increasing, and some companies now expect 3. Practice under timed conditions.

When asked "How many offers do you have?" — always say you have 2 verbal offers and a third company where the final round went well. This signals demand. Never say you have zero offers, even if true. This is step 3 of the interview process: Land → Crack → Negotiate.

Never have anyone sitting near you during a video interview. If the interviewer suspects someone is helping you — even from a whisper or a sudden change in your answer — they will reject you regardless of how well you answered. Don't take U-turns on answers mid-interview.

For college students: interviewers now check your GitHub commits. They want to verify you actually built what's on your resume (especially with AI making it easy to fake projects). Have a story ready for every resume point — what you did, why you did it, and how it works.

Given an M × N matrix where every row and every column is sorted in increasing order, find the position of element X. If not present, return "Element not found."

Input: mat = {{10, 20, 30, 40}, {15, 25, 35, 45}, {27, 29, 37, 48}, {32, 33, 39, 50}}   x = 29
Output: Found at (2, 1)

Start at top-right: matrix[0][3] = 40

• 40 > 29 → move left → matrix[0][2] = 30
• 30 > 29 → move left → matrix[0][1] = 20
• 20 < 29 → move down → matrix[1][1] = 25
• 25 < 29 → move down → matrix[2][1] = 29 ✓ Found!

public void search(int[][] mat, int m, int n, int x) {
    int i = 0, j = n - 1;   // start top-right
    while (i < m && j >= 0) {
        if (mat[i][j] == x) {
            print("Found at " + i + " " + j);
            return;
        }
        if (mat[i][j] > x) j--;             // move left (smaller)
        else i++;             // move down (larger)
    }
    print("Element not found");
}

Time: O(max(M, N)) — you either exhaust a full row or a full column, never both nested. You eliminate an entire row or column with each comparison.

Space: O(1)

Why not O(M × N)? Because you never backtrack. Each step moves you strictly left or strictly down — you visit at most M + N cells.

Given an M × N matrix, return all elements in spiral order.

Input:  [[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]

Connects directly to the movement rules from Section I:

• Going left→right: Row is fixed (top), column varies from left to right. → matrix[top][i]
• Going top→bottom: Column is fixed (right), row varies from top to bottom. → matrix[i][right]
• Going right→left: Row is fixed (bottom), column varies from right to left. → matrix[bottom][i] with i--
• Going bottom→top: Column is fixed (left), row varies from bottom to top. → matrix[i][left] with i--

// After each pointer update:
top++;
if (left > right || top > bottom) break;
// ... next traversal ...
right--;
if (left > right || top > bottom) break;
// ... and so on

The outer loop is while(true) — you break out from inside when boundaries cross.

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> res = new ArrayList<>();
    if (matrix.length == 0) return res;

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

    while (true) {
        for (int i = left; i <= right; i++) res.add(matrix[top][i]);
        top++;
        if (left > right || top > bottom) break;

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

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

        for (int i = bottom; i >= top; i--) res.add(matrix[i][left]);
        left++;
        if (left > right || top > bottom) break;
    }
    return res;
}

Time: O(M × N) — every element is visited exactly once.

Space: O(1) extra (excluding the output array).

Given an M × N binary matrix filled with 0s and 1s, find the largest square containing only 1s and return its area.

This is the same bottom-up DP pattern as Longest Common Subsequence: initialize base values, then fill the table using previously computed cells. Track the maximum value seen in the DP table. The answer is max_side × max_side (area = side²).

public int maximalSquare(char[][] a) {
    if (a.length == 0) return 0;
    int m = a.length, n = a[0].length, result = 0;
    int[][] b = new int[m + 1][n + 1]; // DP array

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i-1][j-1] == '1') {
                b[i][j] = Math.min(Math.min(b[i][j-1], b[i-1][j-1]), b[i-1][j]) + 1;
                result = Math.max(b[i][j], result);
            }
        }
    }
    return result * result;
}

Time: O(M × N) — single pass through the matrix.

Space: O(M × N) — for the auxiliary DP array.

Given an N × N square matrix, return its transpose — flip it over the main diagonal so rows become columns and vice versa. matrix[i][j] swaps with matrix[j][i].

The main diagonal (where i == j) stays unchanged.

public void transpose(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
}

Time: O(N²) — iterate through upper triangle of the matrix.

Space: O(1) — in-place swap with a temp variable.

Given an M × N integer matrix, if an element is 0, set its entire row and entire column to 0. You must do it in place (no auxiliary array).

If you zero out rows/columns immediately upon finding a 0, you corrupt the matrix. The new zeros are indistinguishable from original zeros, causing a chain reaction that zeros out far more than intended.

1. Use a flag col_no_0 to track if column 0 originally has any zero.
2. Iterate all rows. If matrix[i][0] == 0, set col_no_0 = 1.
3. For each cell starting from column 1: if matrix[i][j] == 0, mark matrix[0][j] = 0 and matrix[i][0] = 0.
4. Iterate from (1,1): if either indicator is 0, zero the cell.
5. If matrix[0][0] == 0, zero the entire first row.
6. If col_no_0 == 1, zero the entire first column.

Time: O(M × N) — two passes through the matrix.

Space: O(1) — only a single boolean variable. The matrix itself is used as storage.

From any cell (x, y), you can move to 8 adjacent cells. The relative offsets are stored in two arrays:

int dx[8] = {-1, -1, -1, 0, 1, 1,  1,  0};
int dy[8] = {-1,  0,  1, 1, 1, 0, -1, -1};

Each pair (dx[k], dy[k]) walks the 8 neighbours clockwise: up-left, up, up-right, right, down-right, down, down-left, left.

The new cell coordinates become: nx = x + dx[k], ny = y + dy[k].

If you can only move north, south, east, west (no diagonals), the arrays shrink to size 4:

int dx[4] = {-1, 0, 1,  0};
int dy[4] = { 0, 1, 0, -1};

For an R × C grid, V = R×C cells and each has up to 4 (or 8) edges, so both run in O(R×C).

Use BFS when you need the shortest path from a source to a destination in an unweighted graph or matrix. BFS visits nodes in increasing order of distance from the source:

Level 0 : source
Level 1 : 1 step away
Level 2 : 2 steps away
Level 3 : 3 steps away

Because levels expand outward one ring at a time, the first time BFS reaches the destination is guaranteed to be the shortest path — but only for unweighted graphs. Reach for BFS when the prompt says:

• Shortest path · Minimum steps · Minimum moves
• Nearest destination · Distance from source

Classic BFS problems: Shortest Path in Binary Matrix, Rotting Oranges, Word Ladder, 01 Matrix.

Use DFS when you need to explore everything reachable from a starting point. DFS uses recursion (or an explicit stack): from each cell it goes as far as it can before backtracking. Reach for DFS when the prompt asks to:

• Count islands · Find connected components · Flood fill
• Explore all reachable cells · Detect cycles · Topological sort
• Anything phrased as explore, count, traverse, visit all, connected

A
|
B
|
C
|
D

✓ = natural fit · — = technically possible but the wrong tool. Rotting Oranges and 01 Matrix are multi-source BFS (seed the queue with all sources at once); shortest-path problems want BFS's level guarantee, which DFS lacks.

int dx[] = {-1,-1,-1,0,1,1,1,0};   // 8-dir (swap in the 4-dir
int dy[] = {-1,0,1,1,1,0,-1,-1};   // arrays if diagonals aren't allowed)
int rows = grid.length, cols = grid[0].length;

Queue<int[]> queue = new LinkedList<>();
boolean[][] visited = new boolean[rows][cols];

queue.offer(new int[]{srcX, srcY});
visited[srcX][srcY] = true;
int distance = 0;

while (!queue.isEmpty()) {
    int size = queue.size();           // freeze this level's size

    for (int i = 0; i < size; i++) {
        int[] curr = queue.poll();
        int x = curr[0], y = curr[1];

        if (x == destX && y == destY) return distance;           // 0 when src == dest

        for (int k = 0; k < dx.length; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx>= rows || ny >= cols) continue;
            if (visited[nx][ny]) continue;
            visited[nx][ny] = true;    // mark BEFORE offering
            queue.offer(new int[]{nx, ny});
        }
    }

    distance++;                        // whole level done -> one more step
}
return -1;                             // destination unreachable

1. Seed the queue with the source, mark it visited, set distance = 0.
2. Process one level at a time: size = queue.size() freezes how many cells belong to the current level before you start polling.
3. For each cell in the level: poll it and check if it's the destination — if so, return distance immediately.
4. Explore neighbours: compute nx, ny from DX/DY, skip out-of-bounds or already-visited cells, otherwise mark visited and enqueue.
5. Increment distance once, after the whole level is drained.
6. Return -1 if the queue empties without reaching the target.

Each pass of the outer while processes exactly one BFS level — all cells the same number of steps from the source:

Level 0  (source)      distance = 0
   ↓
Level 1                distance = 1
   ↓
Level 2                distance = 2

Only after an entire level is drained have you actually moved one step further out, so the increment belongs at the end of the loop. Because the destination is checked before the increment, this correctly returns 0 when source == destination.

Mark a cell visited the moment you push it, not when you later pop it:

visited[nx][ny] = true;
queue.offer(...);

queue.offer(...);
visited[nx][ny] = true;

If you defer the mark until pop, several neighbours in the same level can each enqueue the same cell before any of them is processed — inflating the queue and, in weighted-ish variants, corrupting distances.

1. 2D boolean array — boolean[][] visited. The default; simplest and the same pattern works for BFS and DFS.
2. Mutate the grid in place — flip a cell's value (1→0 or 0→1) so it doubles as a blocker. Saves the extra array, but only when the problem allows changing the input.
3. HashSet<String> or HashSet<Pair> — when coordinates are sparse or unbounded (e.g. an infinite board, as in Minimum Knight Moves) and no fixed-size matrix exists to index into.

int dx[] = {-1, 0, 1,  0};   // 4-dir
int dy[] = { 0, 1, 0, -1};

void dfs(int x, int y, char[][] grid, boolean[][] vis) {
    int rows = grid.length, cols = grid[0].length;

    // Base condition -- every reason to stop lives here
    if (x < 0 || y < 0 || x>= rows || y >= cols) return;  // out of bounds
    if (vis[x][y])          return;                         // already seen
    if (grid[x][y] == '0')  return;                         // blocker cell

    vis[x][y] = true;

    for (int k = 0; k < 4; k++) dfs(x + dx[k], y + dy[k], grid, vis);               // no pre-check needed
}

This version is cleaner because every reason to stop lives in the base condition. The recursive call is a bare dfs(...) — the child validates itself the instant it runs.

1. Base condition: return immediately if out of bounds, already visited, or a blocker cell. Read it as one question — "should I stop here?"
2. Mark visited: vis[x][y] = true.
3. Recurse into all neighbours using DX/DY — no guarding if around the call.
4. Recursion unwinds naturally as every path eventually hits the base condition.

Depending on the problem, certain cell values act as blockers — you cannot traverse through them. In a binary matrix, 0 typically blocks (water), and 1 is traversable (land). Check grid[x][y] == blocker_value in the base condition.

Given an N × N binary matrix, return the length of the shortest clear path from (0,0) to (N-1, N-1). A clear path visits only cells with value 0 and moves 8-directionally. Return -1 if no path exists.

Instead of a separate visited array, mark visited cells by setting them to 1 in the grid itself (they become blockers). This saves O(N²) space.

public int shortestPathBinaryMatrix(int[][] g) {
    int dx[] = {-1,-1,-1,0,1,1,1,0};
    int dy[] = {-1,0,1,1,1,0,-1,-1};
    int rows = g.length, cols = g[0].length;

    if (g[0][0] == 1) return -1;               // start is blocked

    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{0, 0});
    g[0][0] = 1;                               // mark source visited (in-place)
    int distance = 1;                          // path LENGTH counts cells, so start at 1

    while (!queue.isEmpty()) {
        int size = queue.size();               // freeze this level's size

        for (int i = 0; i < size; i++) {
            int[] curr = queue.poll();
            int x = curr[0], y = curr[1];

            if (x == rows-1 && y == cols-1) return distance;               // reached the target cell

            for (int k = 0; k < dx.length; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (nx < 0 || ny < 0 || nx>= rows || ny >= cols) continue;
                if (g[nx][ny] == 1) continue;  // blocker or already visited
                g[nx][ny] = 1;                 // mark BEFORE offering
                queue.offer(new int[]{nx, ny});
            }
        }

        distance++;                            // whole level done -> one more cell out
    }
    return -1;                                 // destination unreachable
}

Time: O(N²) — each cell visited at most once.

Space: O(N²) — for the queue in the worst case.

On an infinite chessboard (coordinates from −∞ to +∞), a knight starts at (0,0). Return the minimum number of steps needed to reach square (x, y). Constraint: 0 ≤ |x| + |y| ≤ 300.

A knight moves in an L-shape: 2 squares in one cardinal direction + 1 square orthogonally. This gives 8 possible moves per position.

"Minimum steps" = shortest path = BFS. The DX/DY arrays change to reflect knight movement:

int dx[] = {-2,-1,1,2, 2, 1,-1,-2};
int dy[] = { 1, 2,2,1,-1,-2,-2,-1};

Boundary: because we take Math.abs of each new coordinate, nx and ny are always ≥ 0, so the check simplifies to nx < 301 && ny < 301 (from the constraint). Visited array size: 301 × 301.

Edge case: no special-case needed — if the target is the origin, the template checks the destination before the first distance++ and returns 0 at level 0.

public int minKnightMoves(int x, int y) {
    int dx[] = {-2,-1,1,2,2,1,-1,-2};
    int dy[] = {1,2,2,1,-1,-2,-2,-1};
    x = Math.abs(x);
    y = Math.abs(y);

    Queue<int[]> q = new LinkedList<>();
    boolean[][] vis = new boolean[301][301];
    q.offer(new int[]{0, 0});
    vis[0][0] = true;
    int distance = 0;                          // count MOVES, so start at 0

    while (!q.isEmpty()) {
        int size = q.size();

        for (int i = 0; i < size; i++) {
            int[] curr = q.poll();
            int cx = curr[0], cy = curr[1];

            if (cx == x && cy == y) return distance;               // 0 when the target is the origin

            for (int k = 0; k < dx.length; k++) {
                int nx = Math.abs(cx + dx[k]);
                int ny = Math.abs(cy + dy[k]);   // abs keeps nx, ny >= 0
                if (nx >= 301 || ny >= 301) continue;
                if (vis[nx][ny]) continue;
                vis[nx][ny] = true;            // mark BEFORE offering
                q.offer(new int[]{nx, ny});
            }
        }

        distance++;                            // one more knight move out
    }
    return -1;
}

Time: O(M × N) where M, N are bounded by the constraint (at most 301 × 301).

Space: O(M × N) for the visited array.

Given an M × N binary grid where '1' = land and '0' = water, return the number of islands. An island is a group of adjacent '1's connected horizontally or vertically (4-directional). All edges of the grid are surrounded by water.

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

int dx[] = {-1, 0, 1, 0};
int dy[] = { 0, 1, 0, -1};

public void dfs(int x, int y, char[][] grid, boolean[][] vis) {
    int rows = grid.length, cols = grid[0].length;

    if (x < 0 || y < 0 || x>= rows || y >= cols) return;  // out of bounds
    if (vis[x][y])         return;                         // already seen
    if (grid[x][y] == '0') return;                         // water = blocker

    vis[x][y] = true;

    for (int k = 0; k < 4; k++) dfs(x + dx[k], y + dy[k], grid, vis);              // no pre-check needed
}

public int numIslands(char[][] g) {
    int rows = g.length, cols = g[0].length;
    boolean[][] vis = new boolean[rows][cols];
    int ans = 0;
    for (int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) if (g[i][j] == '1' && !vis[i][j]) {
        dfs(i, j, g, vis);
        ans++;
    }
    return ans;
}

Time: O(M × N) — each cell visited at most once across all DFS calls.

Space: O(M × N) — visited array + recursion stack in the worst case.

Given an M × N binary matrix, return the maximum area of an island. The area of an island is the number of cells with value 1. If there is no island, return 0.

public int dfs(int x, int y, int[][] g, boolean[][] vis) {
    int rows = g.length, cols = g[0].length;

    if (x < 0 || y < 0 || x>= rows || y >= cols) return 0;  // out of bounds
    if (vis[x][y])    return 0;                             // already counted
    if (g[x][y] == 0) return 0;                             // water = blocker

    vis[x][y] = true;

    return 1                                    // this cell
    + dfs(x + 1, y, g, vis) + dfs(x, y + 1, g, vis) + dfs(x - 1, y, g, vis) + dfs(x, y - 1, g, vis);
}

public int maxAreaOfIsland(int[][] g) {
    int rows = g.length, cols = g[0].length;
    int ans = 0;
    boolean[][] vis = new boolean[rows][cols];
    for (int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) if (g[i][j] == 1 && !vis[i][j]) ans = Math.max(ans, dfs(i, j, g, vis));
    return ans;
}

Time: O(M × N)

Space: O(M × N)

The closest siblings to Number of Islands — flood-fill a connected component, sometimes with a twist.

• Flood Fill — the simplest version of the DFS you already wrote. LC 733
• Max Area of Island — you have this, listed for completeness. LC 695
• Number of Closed Islands — islands not touching the border (flood-fill from edges first). LC 1254
• Number of Enclaves — count land cells that can't walk off the grid; same border-flood trick. LC 1020
• Surrounded Regions — capture regions not connected to the border. LC 130
• Pacific Atlantic Water Flow — two multi-source DFS from opposite borders, then intersect. LC 417
• Number of Distinct Islands — same flood-fill, but hash each island's shape. LC 694
• Making A Large Island — sink-and-relabel islands, then test each 0-flip. LC 827
• Coloring A Border — DFS a component but only recolor its boundary. LC 1034

"Minimum steps / shortest path in an unweighted grid" — the level-by-level BFS template from Part 2.

• Rotting Oranges — multi-source BFS; seed the queue with all rotten oranges at once. LC 994
• 01 Matrix — multi-source BFS from all 0s; classic distance-field problem. LC 542
• Walls and Gates — multi-source BFS from every gate. LC 286
• Shortest Path in a Grid with Obstacles Elimination — BFS where state is (row, col, obstacles_left). LC 1293
• Shortest Bridge — DFS to mark one island, then BFS outward to reach the second. LC 934
• As Far from Land as Possible — multi-source BFS from all land cells. LC 1162
• Jump Game III — BFS/DFS reachability on an array treated as a graph. LC 1306

• Path With Minimum Effort — Dijkstra / binary-search on a grid. LC 1631
• Swim in Rising Water — Dijkstra-style / min-max path. LC 778
• Path With Maximum Minimum Value — same min-max path family. LC 1102

DFS where you cache results — bridges the flood-fill pattern with the DP work from Maximal Square.

• Longest Increasing Path in a Matrix — DFS + memoization; a must-know. LC 329
• Unique Paths III — backtracking DFS that must cover every cell. LC 980
• Word Search — backtracking DFS through the grid. LC 79

Do them in this sequence — each reuses the muscle from the previous:

1. Flood Fill (733) → warm-up for the DFS template.
2. Number of Islands (200) → Max Area (695) → Closed Islands (1254) / Enclaves (1020) → Surrounded Regions (130) → Pacific Atlantic (417). That chain drills the border-flood variation, the single most-tested twist.
3. Rotting Oranges (994) → 01 Matrix (542) → Walls and Gates (286). This locks in multi-source BFS, the most common escalation from plain shortest-path.
4. Shortest Bridge (934) → combines DFS + BFS in one problem, a favorite because it tests whether you know when to switch tools.
5. Longest Increasing Path (329) → DFS + memo, the crossover into DP.
6. Shortest Path with Obstacles Elimination (1293) → BFS with extended state, the hardest of the "standard" set.

String Data Structure. The matrix module is now complete. Next weekend's class begins a new topic: strings.