Quick Overview

Maximize rocks collected from the bottom-left to the top-right of a grid using only upward and rightward moves.

Collect the Most Rocks with Upward and Rightward Moves

Company: Goldman Sachs

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

A rectangular grid contains a nonnegative number of rocks in each cell. For this practice version, begin at the bottom-left cell and finish at the top-right cell. You may move only one cell right or one cell up at a time. Return the largest total number of rocks you can collect on a valid path. Collect the rocks in every visited cell, including the starting and ending cells. ### Input - `rocks`: a nonempty two-dimensional integer array. Row `0` is the top row, and column `0` is the leftmost column. ### Output Return the maximum collectible total as an integer. ### Constraints and Edge Cases - For this practice version, the grid has between `1` and `200` rows and between `1` and `200` columns. - Each cell contains between `0` and `1000000` rocks. - There are no blocked cells. - Movement cannot go left or down. A path therefore never revisits a cell. - In a one-cell grid, return that cell's rock count. - In a single row or column, the only valid path visits every cell. ### Example 1 ```text rocks = [[1,2,3], [4,5,6]] output = 18 ``` Move right across the bottom row, then up to the destination: `4 + 5 + 6 + 3 = 18`. ### Example 2 ```text rocks = [[5], [0], [7]] output = 12 ``` The only path moves upward through all three cells and collects `7 + 0 + 5` rocks.

Overview: Maximize rocks collected from the bottom-left to the top-right of a grid using only upward and rightward moves.

A rectangular grid contains a nonnegative number of rocks in each cell. For this practice version, begin at the bottom-left cell and finish at the top-right cell. You may move only one cell right or one cell up at a time. Return the largest total number of rocks you can collect on a valid path. Collect the rocks in every visited cell, including the starting and ending cells. ### Input - `rocks`: a nonempty two-dimensional integer array. Row `0` is the top row, and column `0` is the leftmost column. ### Output Return the maximum collectible total as an integer. ### Constraints and Edge Cases - For this practice version, the grid has between `1` and `200` rows and between `1` and `200` columns. - Each cell contains between `0` and `1000000` rocks. - There are no blocked cells. - Movement cannot go left or down. A path therefore never revisits a cell. - In a one-cell grid, return that cell's rock count. - In a single row or column, the only valid path visits every cell. ### Example 1 ```text rocks = [[1,2,3], [4,5,6]] output = 18 ``` Move right across the bottom row, then up to the destination: `4 + 5 + 6 + 3 = 18`. ### Example 2 ```text rocks = [[5], [0], [7]] output = 12 ``` The only path moves upward through all three cells and collects `7 + 0 + 5` rocks.

Constraints

  • rocks is a nonempty rectangular integer matrix with 1 through 200 rows and 1 through 200 columns.
  • Every cell contains 0 through 1000000 rocks.
  • Row 0 is the top row. Start at bottom-left and finish at top-right. Move one cell up or right at each step.
  • There are no blocked cells. Include both endpoints; return only the maximum total.

Examples

Input: ([[1, 2, 3], [4, 5, 6]],)

Expected Output: 18

Explanation: Published sample 1: bottom row then upward gives 4+5+6+3=18.

Input: ([[5], [0], [7]],)

Expected Output: 12

Explanation: Published sample 2: the sole path totals 7+0+5=12.

Loading coding console...

Show the approach

Approach

Process rows from bottom to top and columns from left to right. Let dp[col] hold the best total reaching the cell at the current column. Before that cell is updated, dp[col] still represents the cell directly below; after the previous column is updated, dp[col-1] represents the cell directly to the left.

On the bottom row, only the left predecessor is available, so build prefix sums starting at the bottom-left cell. On the first column of higher rows, only the below predecessor is available, so add the current value to dp[0]. At every other cell, add its rock count to the larger of the below and left totals. After the top row is processed, return the last dp entry.

Every valid path to an interior cell ends with an up move from below or a right move from the left. Assuming those predecessor totals are optimal, choosing their maximum and adding this cell gives exactly the optimum here. The boundary updates cover the only available predecessor, and the initial cell counts its own rocks once. Induction in the processing order proves the final total is optimal. Multiple optimal paths need no tie-breaking because only their score is returned.

The grid is never modified. Each cell is processed once, for O(rows * columns) time and O(columns) auxiliary space. A path visits exactly rows + columns - 1 cells, so the largest valid answer is 399000000; signed 32-bit Java and C++ integers and JavaScript numbers represent it exactly.

Time complexity:
O(rows * columns).
Space complexity:
O(columns) auxiliary space.