Autocoder

Matrix interview questions with worked solutions

Last updated 2026-11-19

Matrix problems are array problems in two dimensions, and most of the difficulty is in the indexing. The same few ideas keep returning: traverse in a fixed pattern (rows, spirals, diagonals), transform in place using symmetry, treat the grid as a graph for flood fill and BFS, and exploit sorted rows and columns to search quickly.

The ten problems below mix all four. For BFS on a grid see queue and deque questions, and for 2D prefix sums see prefix sum questions. Practice tips for timed tests are in the DSA coding round guide.

Problems10, easy to hard
LanguagesPython and Java
PatternsBoundaries, symmetry, flood fill, staircase search

Indexing habits that prevent bugs

Name dimensions once (R rows, C columns) and write m[i][j] with i for the row and j for the column every time. Check whether the matrix can be empty or non-square before assuming n by n. For neighbours, use a direction list [(1,0), (-1,0), (0,1), (0,-1)] and one bounds check rather than four hand-written cases.

For in-place transformations, ask what information you would overwrite before you have used it. The standard answers are a marker row and column, extra encoded states, or a symmetric swap.

Common mistakes

Mixing up row and column counts on non-square input, forgetting that spiral loops need guards for single rows and columns, and mutating the input while still needing the original values (as in Game of Life). Mention complexity in terms of R and C, not just n.

Matrix interview questions with worked solutions: questions with worked answers

  1. 1

    Transpose a matrix (which may be non-square).

    easy

    The element at row i, column j moves to row j, column i. A non-square matrix needs a new C by R matrix, because the shape changes. Square matrices can be transposed in place by swapping above-diagonal entries with their mirror. Time O(R * C), space O(R * C) for the result.. Edge cases: one row or one column, empty matrix, square input.

    python
    def transpose(m):
        R, C = len(m), len(m[0])
        return [[m[i][j] for i in range(R)] for j in range(C)]
    java
    import java.util.*;
    
    class Solution {
        static int[][] transpose(int[][] m) {
            int R = m.length, C = m[0].length;
            int[][] t = new int[C][R];
            for (int i = 0; i < R; i++)
                for (int j = 0; j < C; j++) t[j][i] = m[i][j];
            return t;
        }
    }
  2. 2

    Rotate an n by n image 90 degrees clockwise in place.

    medium

    A clockwise rotation equals a transpose followed by reversing each row. Transpose by swapping m[i][j] with m[j][i] for j > i, then reverse every row. For [[1,2],[3,4]] the transpose is [[1,3],[2,4]] and reversing rows gives [[3,1],[4,2]]. Time O(n^2), space O(1).. Edge cases: n = 1, even and odd n, counter-clockwise rotation (transpose, then reverse columns, or reverse rows first).

    python
    def rotate(m):
        n = len(m)
        for i in range(n):
            for j in range(i + 1, n):
                m[i][j], m[j][i] = m[j][i], m[i][j]
        for row in m:
            row.reverse()
    java
    import java.util.*;
    
    class Solution {
        static void rotate(int[][] m) {
            int n = m.length;
            for (int i = 0; i < n; i++)
                for (int j = i + 1; j < n; j++) {
                    int t = m[i][j]; m[i][j] = m[j][i]; m[j][i] = t;
                }
            for (int[] row : m)
                for (int l = 0, r = n - 1; l < r; l++, r--) {
                    int t = row[l]; row[l] = row[r]; row[r] = t;
                }
        }
    }
  3. 3

    Spiral matrix: return all elements in spiral order.

    medium

    Keep four boundaries: top, bottom, left, right. Walk the top row left to right and move top down; walk the right column and move right in; if rows remain walk the bottom row right to left; if columns remain walk the left column bottom to top. Repeat while the boundaries have not crossed. The two guards matter for a single row or column. Time O(R * C), space O(1) beyond the output.. Edge cases: single row, single column, non-square matrix, empty matrix.

    python
    def spiral_order(m):
        if not m:
            return []
        res = []
        t, b, l, r = 0, len(m) - 1, 0, len(m[0]) - 1
        while t <= b and l <= r:
            for j in range(l, r + 1):
                res.append(m[t][j])
            t += 1
            for i in range(t, b + 1):
                res.append(m[i][r])
            r -= 1
            if t <= b:
                for j in range(r, l - 1, -1):
                    res.append(m[b][j])
                b -= 1
            if l <= r:
                for i in range(b, t - 1, -1):
                    res.append(m[i][l])
                l += 1
        return res
    java
    import java.util.*;
    
    class Solution {
        static List<Integer> spiralOrder(int[][] m) {
            List<Integer> res = new ArrayList<>();
            if (m.length == 0) return res;
            int t = 0, b = m.length - 1, l = 0, r = m[0].length - 1;
            while (t <= b && l <= r) {
                for (int j = l; j <= r; j++) res.add(m[t][j]);
                t++;
                for (int i = t; i <= b; i++) res.add(m[i][r]);
                r--;
                if (t <= b) { for (int j = r; j >= l; j--) res.add(m[b][j]); b--; }
                if (l <= r) { for (int i = b; i >= t; i--) res.add(m[i][l]); l++; }
            }
            return res;
        }
    }
  4. 4

    Set matrix zeroes: if a cell is 0, set its entire row and column to 0, in O(1) extra space.

    medium

    Use the first row and first column as markers. First record whether the first row and first column themselves contain a zero. Then for every other cell that is zero, mark its row header and column header. Next zero out all other cells whose header is marked. Finally zero the first row and column if they originally held a zero. Time O(R * C), space O(1).. Edge cases: zero in the first row or column only, all zeroes, a one-row or one-column matrix.

    python
    def set_zeroes(m):
        R, C = len(m), len(m[0])
        first_row = any(m[0][j] == 0 for j in range(C))
        first_col = any(m[i][0] == 0 for i in range(R))
        for i in range(1, R):
            for j in range(1, C):
                if m[i][j] == 0:
                    m[i][0] = m[0][j] = 0
        for i in range(1, R):
            for j in range(1, C):
                if m[i][0] == 0 or m[0][j] == 0:
                    m[i][j] = 0
        if first_row:
            for j in range(C):
                m[0][j] = 0
        if first_col:
            for i in range(R):
                m[i][0] = 0
    java
    import java.util.*;
    
    class Solution {
        static void setZeroes(int[][] m) {
            int R = m.length, C = m[0].length;
            boolean firstRow = false, firstCol = false;
            for (int j = 0; j < C; j++) if (m[0][j] == 0) firstRow = true;
            for (int i = 0; i < R; i++) if (m[i][0] == 0) firstCol = true;
            for (int i = 1; i < R; i++)
                for (int j = 1; j < C; j++)
                    if (m[i][j] == 0) { m[i][0] = 0; m[0][j] = 0; }
            for (int i = 1; i < R; i++)
                for (int j = 1; j < C; j++)
                    if (m[i][0] == 0 || m[0][j] == 0) m[i][j] = 0;
            if (firstRow) for (int j = 0; j < C; j++) m[0][j] = 0;
            if (firstCol) for (int i = 0; i < R; i++) m[i][0] = 0;
        }
    }
  5. 5

    Search a matrix where each row is sorted and each row starts after the previous row ends.

    medium

    The matrix behaves like one sorted array of R * C items laid out row by row. Binary search on the flattened index: mid maps to row mid // C and column mid % C. No flattening is actually built. Time O(log(R * C)), space O(1).. Edge cases: empty matrix, a single element, target outside the range.

    python
    def search_matrix(m, target):
        if not m or not m[0]:
            return False
        R, C = len(m), len(m[0])
        lo, hi = 0, R * C - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            v = m[mid // C][mid % C]
            if v == target:
                return True
            if v < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return False
    java
    import java.util.*;
    
    class Solution {
        static boolean searchMatrix(int[][] m, int target) {
            if (m.length == 0 || m[0].length == 0) return false;
            int R = m.length, C = m[0].length, lo = 0, hi = R * C - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                int v = m[mid / C][mid % C];
                if (v == target) return true;
                if (v < target) lo = mid + 1;
                else hi = mid - 1;
            }
            return false;
        }
    }
  6. 6

    Search a matrix where rows and columns are each sorted, but rows do not chain.

    medium

    Start at the top-right corner. If the value equals the target, done. If it is larger than the target, nothing below it in its column can match, so move left; if smaller, nothing to its left in its row can match, so move down. Each step discards a row or a column. Time O(R + C), space O(1).. Edge cases: target absent, a single row or column, target in a corner.

    python
    def search_matrix_ii(m, target):
        if not m or not m[0]:
            return False
        r, c = 0, len(m[0]) - 1
        while r < len(m) and c >= 0:
            v = m[r][c]
            if v == target:
                return True
            if v > target:
                c -= 1
            else:
                r += 1
        return False
    java
    import java.util.*;
    
    class Solution {
        static boolean searchMatrixII(int[][] m, int target) {
            if (m.length == 0 || m[0].length == 0) return false;
            int r = 0, c = m[0].length - 1;
            while (r < m.length && c >= 0) {
                int v = m[r][c];
                if (v == target) return true;
                if (v > target) c--;
                else r++;
            }
            return false;
        }
    }
  7. 7

    Number of islands: count connected groups of 1s (4-directional) in a grid of characters.

    medium

    Scan every cell. When you find a land cell, count one island and sink the whole island with DFS, setting each visited land cell to water so it is not counted again. The count at the end is the answer. BFS works equally well and avoids deep recursion. Time O(R * C), space O(R * C) recursion in the worst case.. Edge cases: empty grid, all water, one big island, diagonal neighbours do not connect.

    python
    def num_islands(g):
        if not g:
            return 0
        R, C = len(g), len(g[0])
        def sink(r, c):
            if r < 0 or c < 0 or r >= R or c >= C or g[r][c] != '1':
                return
            g[r][c] = '0'
            sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1)
        count = 0
        for i in range(R):
            for j in range(C):
                if g[i][j] == '1':
                    count += 1
                    sink(i, j)
        return count
    java
    import java.util.*;
    
    class Solution {
        static int numIslands(char[][] g) {
            int count = 0;
            for (int i = 0; i < g.length; i++)
                for (int j = 0; j < g[0].length; j++)
                    if (g[i][j] == '1') {
                        count++;
                        sink(g, i, j);
                    }
            return count;
        }
        static void sink(char[][] g, int r, int c) {
            if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return;
            g[r][c] = '0';
            sink(g, r + 1, c); sink(g, r - 1, c); sink(g, r, c + 1); sink(g, r, c - 1);
        }
    }
  8. 8

    Valid Sudoku: check that a partially filled 9 by 9 board has no repeated digit in any row, column or box.

    medium

    Keep a set for each of the 9 rows, 9 columns and 9 boxes. For every filled cell, compute its box index as (r // 3) * 3 + c // 3, and fail if the digit is already in any of its three sets. You are only validating the filled cells, not solving the board. Time O(81) = O(1), space O(81).. Edge cases: all empty cells, a duplicate only inside a box, digits repeated across different rows being fine.

    python
    def is_valid_sudoku(b):
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]
        for r in range(9):
            for c in range(9):
                d = b[r][c]
                if d == '.':
                    continue
                k = r // 3 * 3 + c // 3
                if d in rows[r] or d in cols[c] or d in boxes[k]:
                    return False
                rows[r].add(d); cols[c].add(d); boxes[k].add(d)
        return True
    java
    import java.util.*;
    
    class Solution {
        static boolean isValidSudoku(char[][] b) {
            boolean[][] rows = new boolean[9][9], cols = new boolean[9][9], boxes = new boolean[9][9];
            for (int r = 0; r < 9; r++)
                for (int c = 0; c < 9; c++) {
                    if (b[r][c] == '.') continue;
                    int d = b[r][c] - '1', k = r / 3 * 3 + c / 3;
                    if (rows[r][d] || cols[c][d] || boxes[k][d]) return false;
                    rows[r][d] = cols[c][d] = boxes[k][d] = true;
                }
            return true;
        }
    }
  9. 9

    Game of Life: compute the next board state in place, all cells updating at once.

    hard

    You cannot overwrite a cell until its neighbours have used the old value. Encode transitions in the same cell: 2 means was alive and dies, 3 means was dead and becomes alive. When counting neighbours treat 1 and 2 as alive (they were alive before). After one full pass, take each value modulo 2 to get the new state. Time O(R * C), space O(1).. Edge cases: a cell on the border or corner, a single row, a still life that does not change.

    python
    def game_of_life(b):
        R, C = len(b), len(b[0])
        for i in range(R):
            for j in range(C):
                live = 0
                for di in (-1, 0, 1):
                    for dj in (-1, 0, 1):
                        if (di or dj) and 0 <= i + di < R and 0 <= j + dj < C:
                            live += b[i + di][j + dj] in (1, 2)
                if b[i][j] == 1 and live not in (2, 3):
                    b[i][j] = 2
                elif b[i][j] == 0 and live == 3:
                    b[i][j] = 3
        for i in range(R):
            for j in range(C):
                b[i][j] %= 2
    java
    import java.util.*;
    
    class Solution {
        static void gameOfLife(int[][] b) {
            int R = b.length, C = b[0].length;
            for (int i = 0; i < R; i++)
                for (int j = 0; j < C; j++) {
                    int live = 0;
                    for (int di = -1; di <= 1; di++)
                        for (int dj = -1; dj <= 1; dj++) {
                            int x = i + di, y = j + dj;
                            if ((di != 0 || dj != 0) && x >= 0 && x < R && y >= 0 && y < C
                                    && (b[x][y] == 1 || b[x][y] == 2)) live++;
                        }
                    if (b[i][j] == 1 && (live < 2 || live > 3)) b[i][j] = 2;
                    else if (b[i][j] == 0 && live == 3) b[i][j] = 3;
                }
            for (int i = 0; i < R; i++)
                for (int j = 0; j < C; j++) b[i][j] %= 2;
        }
    }
  10. 10

    Kth smallest element in a matrix whose rows and columns are sorted.

    hard

    Binary search on the value, not the index. For a candidate value mid, count how many elements are at most mid using the staircase walk from the bottom-left corner. If the count is at least k, the answer is mid or smaller; otherwise it is larger. The loop ends on a value that exists in the matrix. Time O(n log(max - min)) for an n by n matrix, space O(1).. Edge cases: k = 1 (top-left), k = n * n (bottom-right), duplicate values.

    python
    def kth_smallest(m, k):
        n = len(m)
        def count_le(x):
            r, c, cnt = n - 1, 0, 0
            while r >= 0 and c < n:
                if m[r][c] <= x:
                    cnt += r + 1
                    c += 1
                else:
                    r -= 1
            return cnt
        lo, hi = m[0][0], m[-1][-1]
        while lo < hi:
            mid = (lo + hi) // 2
            if count_le(mid) >= k:
                hi = mid
            else:
                lo = mid + 1
        return lo
    java
    import java.util.*;
    
    class Solution {
        static int kthSmallest(int[][] m, int k) {
            int n = m.length, lo = m[0][0], hi = m[n - 1][n - 1];
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                int r = n - 1, c = 0, cnt = 0;
                while (r >= 0 && c < n) {
                    if (m[r][c] <= mid) { cnt += r + 1; c++; }
                    else r--;
                }
                if (cnt >= k) hi = mid;
                else lo = mid + 1;
            }
            return lo;
        }
    }

Frequently asked questions

How do I loop over neighbours cleanly?

Use a list of direction offsets such as ((1,0),(-1,0),(0,1),(0,-1)) and a single bounds check. Add the four diagonals when the problem allows 8-directional moves.

DFS or BFS for grid problems?

DFS is shorter to write but can overflow the stack on big grids. BFS uses a queue and is needed for shortest paths. See queue and deque questions.

What is the cost of rotating a matrix in place?

O(n^2) time and O(1) space with transpose plus row reversal. Allocating a second matrix is simpler but O(n^2) space.

How do I tell the two matrix search problems apart?

If every row starts after the previous ends, binary search the flattened index. If only rows and columns are sorted, use the staircase walk from a corner.

Where do grid DP problems fit?

Minimum path sum, unique paths and maximal square are dynamic programming on a matrix. See dynamic programming questions.

Related guides

More in DSA Interview Questions

See all in this section