Scale Engineer

Grid Game

Med
#1837Time: O(n^2), where n is the number of columns. The outer loop runs `n` times. Inside the loop, we have two more loops to calculate the sums, each taking up to O(n) time.Space: O(1), as we only use a few variables to store the sums and the result, regardless of the input size.
Patterns
Prefix Sum
Data structures
ArrayMatrix

Prompt

You are given a 0-indexed 2D array grid of size 2 x n, where grid[r][c] represents the number of points at position (r, c) on the matrix. Two robots are playing a game on this matrix.

Both robots initially start at (0, 0) and want to reach (1, n-1). Each robot may only move to the right ((r, c) to (r, c + 1)) or down ((r, c) to (r + 1, c)).

At the start of the game, the first robot moves from (0, 0) to (1, n-1), collecting all the points from the cells on its path. For all cells (r, c) traversed on the path, grid[r][c] is set to 0. Then, the second robot moves from (0, 0) to (1, n-1), collecting the points on its path. Note that their paths may intersect with one another.

The first robot wants to minimize the number of points collected by the second robot. In contrast, the second robot wants to maximize the number of points it collects. If both robots play optimally, return the number of points collected by the second robot.

 

Example 1:

Input: grid = [[2,5,4],[1,5,1]]
Output: 4
Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 0 + 4 + 0 = 4 points.

Example 2:

Input: grid = [[3,3,1],[8,5,2]]
Output: 4
Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 3 + 1 + 0 = 4 points.

Example 3:

Input: grid = [[1,3,1,15],[1,3,3,1]]
Output: 7
Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 1 + 3 + 3 + 0 = 7 points.

 

Constraints:

  • grid.length == 2
  • n == grid[r].length
  • 1 <= n <= 5 * 104
  • 1 <= grid[r][c] <= 105

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the game based on our understanding of the optimal strategies. The first robot can choose n different paths, each defined by the column i where it moves from the top row to the bottom row. For each of these n choices, we calculate the maximum score the second robot can achieve and then find the minimum among these scores.

Algorithm

  • Initialize minResult to a very large number (e.g., Long.MAX_VALUE).
  • Iterate i from 0 to n-1, where n is the number of columns. This i represents the column where the first robot switches from the top row to the bottom row.
  • Inside the loop, for each i:
    • Initialize topSum = 0 and bottomSum = 0.
    • Calculate topSum by iterating from j = i + 1 to n-1 and summing up grid[0][j].
    • Calculate bottomSum by iterating from j = 0 to i-1 and summing up grid[1][j].
    • The second robot will choose the path that yields the maximum score, which is max(topSum, bottomSum).
    • The first robot wants to minimize this score, so we update our overall result: minResult = min(minResult, max(topSum, bottomSum)).
  • After the loop finishes, minResult will hold the score of the second robot when both play optimally. Return minResult.

Walkthrough

The core idea is to iterate through every possible path for the first robot. A path is uniquely determined by the column i (from 0 to n-1) where the robot switches from row 0 to row 1.

For a fixed i, the first robot clears the path (0,0) -> ... -> (0,i) -> (1,i) -> ... -> (1,n-1). After this, the grid is effectively split into two sections of available points for the second robot:

  1. The points in the top row to the right of column i: grid[0][i+1] to grid[0][n-1].
  2. The points in the bottom row to the left of column i: grid[1][0] to grid[1][i-1].

The second robot, to maximize its score, will choose a path that collects all points from one of these two sections. Its score will be the maximum of the sum of points in these two sections.

We can iterate through each possible i from 0 to n-1. In each iteration, we calculate the sum of the top-right part and the bottom-left part. We take the maximum of these two sums, which is the score the second robot gets for this i. We keep track of the minimum of these maximum scores over all i. This minimum value is the answer, as the first robot will choose the i that leads to this outcome.

class Solution {    public long gridGame(int[][] grid) {        int n = grid[0].length;        long minMaxScore = Long.MAX_VALUE;         for (int i = 0; i < n; i++) {            // Simulate Robot 1's path switching at column i                        // Calculate score for Robot 2's top path option            long topPathScore = 0;            for (int j = i + 1; j < n; j++) {                topPathScore += grid[0][j];            }             // Calculate score for Robot 2's bottom path option            long bottomPathScore = 0;            for (int j = 0; j < i; j++) {                bottomPathScore += grid[1][j];            }             // Robot 2 chooses the path with the maximum score            long secondRobotScore = Math.max(topPathScore, bottomPathScore);             // Robot 1 chooses i to minimize Robot 2's score            minMaxScore = Math.min(minMaxScore, secondRobotScore);        }         return minMaxScore;    }}

Complexity

Time

O(n^2), where n is the number of columns. The outer loop runs `n` times. Inside the loop, we have two more loops to calculate the sums, each taking up to O(n) time.

Space

O(1), as we only use a few variables to store the sums and the result, regardless of the input size.

Trade-offs

Pros

  • Simple to understand and implement directly from the problem's logic.

  • It correctly models the game's minimax nature.

Cons

  • This approach is inefficient due to the nested loops, leading to a quadratic time complexity.

  • For the given constraints (n up to 5 * 10^4), this solution will be too slow and result in a 'Time Limit Exceeded' error on most platforms.

Solutions

class Solution {public  long gridGame(int[][] grid) {    long ans = Long.MAX_VALUE;    long s1 = 0, s2 = 0;    for (int v : grid[0]) {      s1 += v;    }    int n = grid[0].length;    for (int j = 0; j < n; ++j) {      s1 -= grid[0][j];      ans = Math.min(ans, Math.max(s1, s2));      s2 += grid[1][j];    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem