Grid path DP — Gold Mine, Min Cost Path, max square submatrix of 1s, maximum sum rectangle
Problem
Grid DP problems:
Gold mine — start anywhere in the first column and move right, up-right or down-right, collecting as much gold as possible. Minimum cost path (Minimum Path Sum) — from the top-left to the bottom-right moving right or down, minimise the sum. Largest square of 1s (Maximal Square). Maximum sum rectangle — the submatrix with the largest sum (Kadane's algorithm over column pairs).
Example 1
Input: min path sum [[1,3,1], [1,5,1], [4,2,1]] Output: 7
1→3→1→1→1.
Example 2
Input: maximal square [["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]] Output: 4
Also asked as: Gold Mine Problem · Min Cost PathProblem · Maximum size square sub-matrix with all 1s · Maximum sum rectangle in a 2D matrix · Largest rectangular sub-matrix whose sum is 0 · Largest area rectangular sub-matrix with equal number of 1’s and 0’s · Assembly Line SchedulingProblem
Test cases
Case 1
Input: [[1,3,3],[2,1,4],[0,6,4]] Expected: 12
Case 2
Input: [[1,3,1,5],[2,2,4,1],[5,0,2,3],[0,6,1,2]] Expected: 16
Case 3
Input: [[7]] Expected: 7
View solutionHide solution3 approaches
1. Gold mine — DP right-to-left over columns
Time O(R·C)Space O(R·C)
From a cell you move right / right-up / right-down. dp[r][c] = grid[r][c] + max of the three reachable cells in column c+1.
function goldMine(grid) { const R = grid.length, C = grid[0].length; const dp = grid.map((row) => row.slice()); for (let c = C - 2; c >= 0; c--) for (let r = 0; r < R; r++) { const right = dp[r][c + 1]; const up = r > 0 ? dp[r - 1][c + 1] : 0; const down = r < R - 1 ? dp[r + 1][c + 1] : 0; dp[r][c] = grid[r][c] + Math.max(right, up, down); } return Math.max(...dp.map((row) => row[0]));}2. Maximum size square submatrix of 1s
Time O(R·C)Space O(R·C)
dp[r][c] = side of the largest all-1s square with its bottom-right corner at (r,c) = 1 + min(top, left, top-left) when grid[r][c] is 1.
function maximalSquare(m) { const R = m.length, C = m[0].length; const dp = Array.from({ length: R + 1 }, () => new Array(C + 1).fill(0)); let best = 0; for (let r = 1; r <= R; r++) for (let c = 1; c <= C; c++) if (m[r - 1][c - 1] === 1) { dp[r][c] = 1 + Math.min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1]); best = Math.max(best, dp[r][c]); } return best * best;}3. Maximum sum rectangle — Kadane over column ranges
Time O(C²·R)Space O(R)
Fix the left and right column; compress each row between them into a single number (row sum); run 1-D Kadane on that array. O(C²·R).
function maxSumRectangle(mat) { const R = mat.length, C = mat[0].length; let best = -Infinity; for (let left = 0; left < C; left++) { const rowSum = new Array(R).fill(0); for (let right = left; right < C; right++) { for (let r = 0; r < R; r++) rowSum[r] += mat[r][right]; let cur = 0, localBest = -Infinity; for (const x of rowSum) { cur = Math.max(x, cur + x); localBest = Math.max(localBest, cur); } best = Math.max(best, localBest); } } return best;}Largest submatrix with sum 0 / equal 0s and 1s: same column-pair trick, but instead of Kadane use a prefix-sum→first-index hashmap on the compressed rows to find the widest zero-sum band (map 0→−1 for the 0s/1s version).