โ† Goldman Sachs questions
CodingReported in a candidate post, Jul 2025

Maximum coins from bottom-left to top-right of a grid

Filed under Goldman Sachs

Free read 2 of 3

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.

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

  1. 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.

Solution

O(m*n) time, O(m*n) space

Python
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.