Maximum coins from bottom-left to top-right of a grid
Filed under Goldman Sachs
Free read 2 of 3Confirm which moves are allowed (right and up?), whether diagonal moves exist, and that coins are non-negative. Fix the orientation: row 0 is the top.
The question
A grid holds a number of gold coins in each cell. Starting at the bottom-left cell, travel to the top-right cell collecting coins from every cell you visit. Return the maximum total. (The report did not give the allowed moves; this assumes moves are only right or up.)
Constraints
- 1 <= rows, cols <= 500
- Coin values are non-negative integers
- Moves allowed: right or up (assumed)
Examples
- Input
- [[1,2,3],[4,5,6],[7,8,9]]
- Output
- 33
- Why
- Row 0 is the top. Path 7 -> 8 -> 9 -> 6 -> 3 collects 33, the best of all right/up paths.
- Input
- [[5]]
- Output
- 5
- Why
- Start and end are the same cell.
Approach
Confirm which moves are allowed (right and up?), whether diagonal moves exist, and that coins are non-negative. Fix the orientation: row 0 is the top.
Recursively try right and up from the start: C(r+c, r) paths, exponential. Many cells are revisited by different paths.
dp[r][c] = grid[r][c] + max(dp[r+1][c], dp[r][c-1]) where those neighbours exist. Fill rows from the bottom up, columns left to right; answer is dp[0][cols-1]. O(rows*cols).
A single row or column, one cell, and all-zero grids. If diagonal moves are allowed, add dp[r+1][c-1] to the max.
Solution
O(m*n) time, O(m*n) space
def max_coins(grid):
m, n = len(grid), len(grid[0])
NEG = float("-inf")
dp = [[0] * n for _ in range(m)] # best total ending at (r, c)
for r in range(m - 1, -1, -1): # start at the bottom row
for c in range(n):
below = dp[r + 1][c] if r + 1 < m else NEG
left = dp[r][c - 1] if c > 0 else NEG
best = max(below, left)
dp[r][c] = grid[r][c] + (0 if best == NEG else best)
return dp[0][n - 1]
Tips
- What they are testing: Whether you recognise grid DP and set the base case and fill order correctly for a start in a non-standard corner.
- Common mistake: Copying the usual top-left to bottom-right DP without flipping the direction, so the loops and base cases are wrong.
Related Goldman Sachs questions
Collected from public candidate posts and coding forums. Updated Nov 2026.