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.
| Problems | 10, easy to hard |
|---|---|
| Languages | Python and Java |
| Patterns | Boundaries, 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.
- Spiral and layer problems: four shrinking boundaries.
- In-place rotation: transpose, then reverse each row.
- Flood fill and islands: DFS or BFS with a visited marker.
- Sorted rows and columns: staircase walk from a corner or binary search on the value.
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 Transpose a matrix (which may be non-square).
easyThe 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.
pythondef transpose(m): R, C = len(m), len(m[0]) return [[m[i][j] for i in range(R)] for j in range(C)]javaimport 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 Rotate an n by n image 90 degrees clockwise in place.
mediumA 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).
pythondef 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()javaimport 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 Spiral matrix: return all elements in spiral order.
mediumKeep 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.
pythondef 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 resjavaimport 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 Set matrix zeroes: if a cell is 0, set its entire row and column to 0, in O(1) extra space.
mediumUse 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.
pythondef 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] = 0javaimport 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 Search a matrix where each row is sorted and each row starts after the previous row ends.
mediumThe 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.
pythondef 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 Falsejavaimport 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 Search a matrix where rows and columns are each sorted, but rows do not chain.
mediumStart 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.
pythondef 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 Falsejavaimport 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 Number of islands: count connected groups of 1s (4-directional) in a grid of characters.
mediumScan 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.
pythondef 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 countjavaimport 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 Valid Sudoku: check that a partially filled 9 by 9 board has no repeated digit in any row, column or box.
mediumKeep 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.
pythondef 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 Truejavaimport 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 Game of Life: compute the next board state in place, all cells updating at once.
hardYou 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.
pythondef 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] %= 2javaimport 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 Kth smallest element in a matrix whose rows and columns are sorted.
hardBinary 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.
pythondef 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 lojavaimport 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
- Array interview questions with worked solutions
- Queue and deque interview questions with worked solutions
- Binary search interview questions with worked solutions
- Prefix sum interview questions with worked solutions
- Recursion interview questions with worked solutions
- Backtracking interview questions with worked solutions
More in DSA Interview Questions
- Merge intervals pattern questions with worked solutions
- Minimum Spanning Tree Interview Questions
- Monotonic stack interview questions with worked solutions
- Prefix sum interview questions with worked solutions
- Queue and deque interview questions with worked solutions
- Recursion interview questions with worked solutions
- Segment Tree Interview Questions
- Sliding window interview questions with worked solutions
- Sorting algorithm interview questions with worked solutions
- Stack interview questions with worked solutions
- String interview questions with worked solutions
- Top K elements interview questions with worked solutions