Grid and Matrix DP Interview Questions
Last updated 2026-11-19
Grid dynamic programming fills a table whose cells depend on their neighbours above and to the left. It covers counting paths, minimising costs along a route, finding squares or rectangles of ones and many other matrix questions. The recurrence is usually short, and the care goes into boundaries.
This page covers eleven grid problems from unique paths to maximal rectangle, each with Python and Java code, complexity and edge cases. The general method is in dynamic programming interview questions, and shortest paths with free movement are in BFS interview questions and Dijkstra interview questions.
| State | dp[i][j] for cell (i, j) |
|---|---|
| Usual order | Row by row, left to right |
| Space trick | One row instead of the whole table |
| Typical cost | O(rows * cols) |
The pattern and when to spot it
Use grid DP when movement is restricted, such as only right and down, or the answer for a cell depends only on cells above and to the left. If you can move in all four directions with varying costs, it is a shortest path problem instead, and Dijkstra or BFS applies. For square and rectangle questions the cell stores a size, and the recurrence uses the minimum of three neighbours.
Direction matters. Some problems, such as the dungeon game, work backwards from the goal because the needed health depends on the future. When each row depends only on the previous row, collapse the table to one array, taking care to save the diagonal value before overwriting it. A prefix sum table turns repeated rectangle sum queries into O(1) operations and is worth recognising as a close cousin of DP.
Common mistakes
- Initialising the first row and column incorrectly, especially with obstacles blocking the rest of the row.
- Forgetting that a rolling row loses the diagonal value unless it is saved first.
- Reading the answer from the corner when the problem asks for the best cell anywhere, as in maximal square.
- Using min or max on infinity sentinels without guarding against overflow in Java.
- Mixing up row and column order when the grid is not square.
Grid and Matrix DP Interview Questions: questions with worked answers
1 Unique paths in an m by n grid
easyA robot moves only right or down, so the number of ways to reach a cell is the sum of the ways to reach the cell above and the cell to its left. The first row and column each have exactly one way. A single row array updated left to right suffices: dp[j] += dp[j-1]. Time O(m * n), space O(n). Edge cases: a 1 by 1 grid (1), a single row or column (1), large grids overflow int so use long or the closed form C(m+n-2, m-1).
pythondef unique_paths(m, n): dp = [1] * n for _ in range(1, m): for j in range(1, n): dp[j] += dp[j - 1] return dp[-1]javaint uniquePaths(int m, int n) { int[] dp = new int[n]; Arrays.fill(dp, 1); for (int i = 1; i < m; i++) for (int j = 1; j < n; j++) dp[j] += dp[j - 1]; return dp[n - 1]; }2 Unique paths with obstacles
mediumA blocked cell has zero ways. Otherwise the ways are the sum of the cell above and to the left. Reuse a one-dimensional array: reset an obstacle cell to 0 and add the left value otherwise. Seed the start with 1 unless it is blocked. Time O(m * n), space O(n). Edge cases: obstacle at the start or the end (0), a fully blocked first row cutting off later columns, a 1 by 1 grid.
pythondef unique_paths_obstacles(grid): n = len(grid[0]) dp = [0] * n dp[0] = 1 if grid[0][0] == 0 else 0 for row in grid: for j in range(n): if row[j] == 1: dp[j] = 0 elif j > 0: dp[j] += dp[j - 1] return dp[-1]javaint uniquePathsObstacles(int[][] grid) { int n = grid[0].length; int[] dp = new int[n]; dp[0] = grid[0][0] == 0 ? 1 : 0; for (int[] row : grid) for (int j = 0; j < n; j++) { if (row[j] == 1) dp[j] = 0; else if (j > 0) dp[j] += dp[j - 1]; } return dp[n - 1]; }3 Minimum path sum from top-left to bottom-right
mediumThe cheapest way into a cell is its own cost plus the cheaper of the cell above and the cell to the left. Edges have only one predecessor. Update a single row in place. Time O(m * n), space O(n). Edge cases: a single row or column (just the sum), negative costs are not allowed by the usual statement, a 1 by 1 grid.
pythondef min_path_sum(grid): n = len(grid[0]) dp = [float('inf')] * n dp[0] = 0 for row in grid: dp[0] += row[0] for j in range(1, n): dp[j] = row[j] + min(dp[j], dp[j - 1]) return dp[-1]javaint minPathSum(int[][] grid) { int n = grid[0].length; int[] dp = new int[n]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; for (int[] row : grid) { dp[0] += row[0]; for (int j = 1; j < n; j++) dp[j] = row[j] + Math.min(dp[j], dp[j - 1]); } return dp[n - 1]; }4 Triangle: minimum path sum from top to bottom
mediumFrom position j in a row you may step to j or j+1 in the next row. Work bottom-up: start with the last row as dp, then for each higher row set dp[j] = triangle[i][j] + min(dp[j], dp[j+1]). The answer is dp[0]. Going bottom-up avoids special handling of edges. Time O(n^2) for n rows, space O(n). Edge cases: a single row, negative numbers, modifying the input to save space is possible but changes the data.
pythondef minimum_total(triangle): dp = triangle[-1][:] for i in range(len(triangle) - 2, -1, -1): for j in range(i + 1): dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]) return dp[0]javaint minimumTotal(List<List<Integer>> t) { int n = t.size(); int[] dp = new int[n]; for (int j = 0; j < n; j++) dp[j] = t.get(n - 1).get(j); for (int i = n - 2; i >= 0; i--) for (int j = 0; j <= i; j++) dp[j] = t.get(i).get(j) + Math.min(dp[j], dp[j + 1]); return dp[0]; }5 Minimum falling path sum
mediumYou may start anywhere in the top row and move down to the cell directly below or diagonally below-left or below-right. Each cell takes its value plus the minimum of the up to three cells above it. The answer is the minimum of the last row. Time O(n^2), space O(n). Edge cases: a 1 by 1 matrix, columns at the edge having only two predecessors, negative values.
pythondef min_falling_path_sum(m): dp = m[0][:] n = len(m) for i in range(1, n): new = [] for j in range(n): best = dp[j] if j > 0: best = min(best, dp[j - 1]) if j < n - 1: best = min(best, dp[j + 1]) new.append(m[i][j] + best) dp = new return min(dp)javaint minFallingPathSum(int[][] m) { int n = m.length; int[] dp = m[0].clone(); for (int i = 1; i < n; i++) { int[] nw = new int[n]; for (int j = 0; j < n; j++) { int best = dp[j]; if (j > 0) best = Math.min(best, dp[j - 1]); if (j < n - 1) best = Math.min(best, dp[j + 1]); nw[j] = m[i][j] + best; } dp = nw; } return Arrays.stream(dp).min().getAsInt(); }6 Maximal square of ones
mediumdp[i][j] is the side of the largest all-ones square whose bottom-right corner is at (i, j). If the cell is 1, it is 1 plus the minimum of the three neighbours above, left and diagonal, because the square is limited by its smallest supporting square. The answer is the largest side squared. Time O(m * n), space O(n). Edge cases: no ones (0), a full matrix of ones (min(m, n) squared), characters instead of integers in the input, keeping the previous diagonal when using one row.
pythondef maximal_square(matrix): n = len(matrix[0]) dp = [0] * (n + 1) best = 0 for row in matrix: prev_diag = 0 for j in range(1, n + 1): tmp = dp[j] if row[j - 1] == '1': dp[j] = 1 + min(dp[j], dp[j - 1], prev_diag) best = max(best, dp[j]) else: dp[j] = 0 prev_diag = tmp return best * bestjavaint maximalSquare(char[][] matrix) { int n = matrix[0].length, best = 0; int[] dp = new int[n + 1]; for (char[] row : matrix) { int prevDiag = 0; for (int j = 1; j <= n; j++) { int tmp = dp[j]; if (row[j - 1] == '1') { dp[j] = 1 + Math.min(dp[j], Math.min(dp[j - 1], prevDiag)); best = Math.max(best, dp[j]); } else dp[j] = 0; prevDiag = tmp; } } return best * best; }7 Count square submatrices with all ones
mediumUse the same table as maximal square. dp[i][j] is the side of the largest square ending at (i, j), and it is also the number of squares ending there (sizes 1 up to dp). Sum all entries. Time O(m * n), space O(m * n). Edge cases: no ones (0), all ones (sum of squares of sizes), sums needing long for large matrices.
pythondef count_squares(matrix): m, n = len(matrix), len(matrix[0]) dp = [[0] * n for _ in range(m)] total = 0 for i in range(m): for j in range(n): if matrix[i][j]: dp[i][j] = 1 if i == 0 or j == 0 else 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) total += dp[i][j] return totaljavaint countSquares(int[][] matrix) { int m = matrix.length, n = matrix[0].length, total = 0; int[][] dp = new int[m][n]; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (matrix[i][j] == 1) { dp[i][j] = (i == 0 || j == 0) ? 1 : 1 + Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])); total += dp[i][j]; } return total; }8 Sum of any submatrix in O(1) using 2D prefix sums
mediumBuild P where P[i][j] is the sum of the rectangle from the origin to (i-1, j-1): P[i][j] = a[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]. A query for rows r1 to r2 and columns c1 to c2 is P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]. Inclusion and exclusion removes the double-counted corner. Time O(m * n) build, O(1) per query, space O(m * n). Edge cases: one-cell queries, whole-matrix queries, negative values, forgetting the extra row and column of zeros.
pythonclass NumMatrix: def __init__(self, a): m, n = len(a), len(a[0]) self.p = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m): for j in range(n): self.p[i+1][j+1] = a[i][j] + self.p[i][j+1] + self.p[i+1][j] - self.p[i][j] def region(self, r1, c1, r2, c2): p = self.p return p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1]javaclass NumMatrix { private final int[][] p; NumMatrix(int[][] a) { int m = a.length, n = a[0].length; p = new int[m + 1][n + 1]; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) p[i+1][j+1] = a[i][j] + p[i][j+1] + p[i+1][j] - p[i][j]; } int region(int r1, int c1, int r2, int c2) { return p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1]; } }9 Out of boundary paths: ways to leave the grid in at most k moves
mediumTrack how many ways there are to stand at each cell after each move, starting with one way at the start. For each move, every cell sends its count to four neighbours; a move that leaves the grid adds to the answer instead. Take results modulo 10^9 + 7. Time O(k * m * n), space O(m * n). Edge cases: k equal to 0 (0), a 1 by 1 grid (4 ways per move), starting on a corner, large counts needing the modulus.
pythondef find_paths(m, n, max_move, r0, c0): MOD = 10**9 + 7 cur = [[0] * n for _ in range(m)] cur[r0][c0] = 1 out = 0 for _ in range(max_move): nxt = [[0] * n for _ in range(m)] for r in range(m): for c in range(n): v = cur[r][c] if not v: continue for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)): nr, nc = r + dr, c + dc if 0 <= nr < m and 0 <= nc < n: nxt[nr][nc] = (nxt[nr][nc] + v) % MOD else: out = (out + v) % MOD cur = nxt return outjavaint findPaths(int m, int n, int maxMove, int r0, int c0) { final int MOD = 1_000_000_007; int[][] cur = new int[m][n]; cur[r0][c0] = 1; long out = 0; int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}}; for (int k = 0; k < maxMove; k++) { int[][] nxt = new int[m][n]; for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) { int v = cur[r][c]; if (v == 0) continue; for (int[] d : dirs) { int nr = r + d[0], nc = c + d[1]; if (nr >= 0 && nr < m && nc >= 0 && nc < n) nxt[nr][nc] = (nxt[nr][nc] + v) % MOD; else out = (out + v) % MOD; } } cur = nxt; } return (int) out; }10 Dungeon game: minimum starting health to reach the princess
hardGoing forward is awkward because you need to know the future. Work backwards from the bottom-right cell. dp[i][j] is the minimum health needed on entering (i, j): max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]). Health must always stay at least 1, which the outer max enforces. Time O(m * n), space O(n). Edge cases: a cell that adds health (the max with 1 caps the need), a destination with a heavy trap, a 1 by 1 grid, treating health as at least 1 at every step.
pythondef calculate_minimum_hp(d): m, n = len(d), len(d[0]) INF = float('inf') dp = [INF] * (n + 1) dp[n - 1] = 1 for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): dp[j] = max(1, min(dp[j], dp[j + 1]) - d[i][j]) dp[n] = INF return dp[0]javaint calculateMinimumHP(int[][] d) { int m = d.length, n = d[0].length; int[] dp = new int[n + 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[n - 1] = 1; for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) dp[j] = Math.max(1, Math.min(dp[j], dp[j + 1]) - d[i][j]); dp[n] = Integer.MAX_VALUE; } return dp[0]; }11 Maximal rectangle of ones in a binary matrix
hardTreat each row as the base of a histogram: heights[j] counts consecutive ones above and including this row, reset to 0 at a zero. For each row, find the largest rectangle in that histogram with a monotonic stack. The answer is the best over all rows. Time O(m * n), space O(n). Edge cases: no ones (0), a single row, a matrix of all ones (m * n), flushing the stack with a sentinel of height 0 at the end of each row.
pythondef maximal_rectangle(matrix): if not matrix: return 0 n = len(matrix[0]) heights = [0] * n best = 0 for row in matrix: for j in range(n): heights[j] = heights[j] + 1 if row[j] == '1' else 0 stack = [] for j in range(n + 1): h = heights[j] if j < n else 0 while stack and heights[stack[-1]] >= h: height = heights[stack.pop()] left = stack[-1] if stack else -1 best = max(best, height * (j - left - 1)) stack.append(j) return bestjavaint maximalRectangle(char[][] matrix) { if (matrix.length == 0) return 0; int n = matrix[0].length, best = 0; int[] heights = new int[n]; for (char[] row : matrix) { for (int j = 0; j < n; j++) heights[j] = row[j] == '1' ? heights[j] + 1 : 0; Deque<Integer> st = new ArrayDeque<>(); for (int j = 0; j <= n; j++) { int h = j < n ? heights[j] : 0; while (!st.isEmpty() && heights[st.peek()] >= h) { int height = heights[st.pop()]; int left = st.isEmpty() ? -1 : st.peek(); best = Math.max(best, height * (j - left - 1)); } st.push(j); } } return best; }
Frequently asked questions
How do I know whether a grid problem is DP or graph search?
If moves are limited to right and down, or each cell depends on earlier cells, use DP. If you can move in any direction with weights, use BFS or Dijkstra.
Can the DP table be reduced to one row?
Yes whenever each row depends only on the previous one. Update in place from left to right, and save the previous diagonal value if the recurrence needs it.
How do I count paths in a grid with obstacles?
Set blocked cells to zero ways and otherwise add the ways from above and from the left. Check that the start and end are not blocked.
Which grid DP problems are asked most?
Unique paths, minimum path sum and maximal square are very common. See the online assessment guide for how coding tests are usually organised.
Related guides
More in DSA Interview Questions
- Hashing interview questions with worked solutions
- Heap and Priority Queue Interview Questions
- Interval DP Interview Questions
- Interval interview questions with worked solutions
- Kadane algorithm interview questions with worked solutions
- KMP and string matching interview questions with solutions
- Knapsack DP Interview Questions
- Linked list interview questions with worked solutions
- Longest Common Subsequence (LCS) Interview Questions
- Longest Increasing Subsequence (LIS) Interview Questions
- LRU Cache and Design Data Structure Interview Questions
- Math and number theory interview questions with solutions