Grid path DP — Gold Mine, Min Cost Path, max square submatrix of 1s, maximum sum rectangle

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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).