2017. Grid Game
Problem Description
In this problem, two robots are playing a game on a 2 x n
grid matrix where each cell contains a certain number of points. The grid is 0-indexed which means that the rows and columns are numbered starting from 0.
Both robots start from the top-left corner at position (0, 0)
and their goal is to reach the bottom-right corner at position (1, n-1)
. They can only move right (from (r, c)
to (r, c + 1)
) or down (from (r, c)
to (r + 1, c)
).
The game is played in two stages:
- The first robot moves first and collects points from each cell it passes through, setting the points in those cells to 0 after passing through them.
- After the first robot finishes its path, the second robot makes its way from
(0, 0)
to(1, n-1)
, collecting remaining points.
The first robot aims to minimize the points that the second robot can collect by choosing an optimal path, while the second robot aims to maximize its points by also choosing an optimal path after the first robot has completed its route.
The objective is to determine the number of points that the second robot will collect if both robots play optimally.
Intuition
The solution is based on the idea that we need to find the path for the first robot that minimizes the maximum points that the second robot can collect. One approach is to simulate the path of the first robot and keep track of the points that will be left for the second robot.
To find the optimal path for the first robot, we need to consider two possible scenarios for the second robot:
- The second robot could take the maximum points from the top row after the first robot completes its path.
- The second robot could take the maximum points from the bottom row after the first robot finishes its path.
We can keep track of two running sums: s1
, for the sum of points left on the top row, and s2
, for the sum of points collected from the bottom row. As we iterate through each column:
- We subtract the points collected by the first robot from
s1
, as those points are no longer available for the second robot. - We then calculate the maximum points the second robot could collect, which is either the remaining points on the top row (
s1
) or the points it has accumulated from the bottom row (s2
), whichever is larger. - We keep track of the minimum such value (
ans
) across all the column iterations since we are looking for the path for the first robot that minimizes the maximum points that the second robot can collect.
The answer we want is this minimum of the maximum points, which is the best that the second robot can do if the first robot plays optimally.
Learn more about Prefix Sum patterns.
Solution Approach
The key algorithm used in this solution is essentially a greedy approach coupled with dynamic programming concepts. We need to keep track of two key metrics as we iterate through the grid: the sum of the remaining points on the top row (s1
) after the first robot moves, and the sum of points on the bottom row that the second robot can potentially collect (s2
). Here's a breakdown of how the algorithm proceeds:
- Initialize
s1
to the sum of all elements in the top row of the grid (this represents the maximum number of points available to the second robot if the first robot drops straight down to the bottom row from the beginning). - Initialize
s2
to 0 as the second robot starts from the first column and has not collected any points yet. - Initialize
ans
toinf
which stands for infinity. This variable will hold the minimum number of points the second robot can collect after the first robot has chosen its path. - Iterate through each column (element) in the top row.
- Subtract the current element's value from
s1
since the first robot will collect these points and they will no longer be available for the second robot. - Calculate the maximum points the second robot can collect after the first robot's move, which is the maximum of
s1
ands2
. This represents the worst-case points that the second robot can get if the first robot moves right on the current step. - Update
ans
with the minimum of itself and the maximum points from the previous step. This effectively stores the best (minimum) outcome for the second robot so far considering all the columns processed. - Add the current element's value from the bottom row to
s2
. This is because the second robot would collect points from the bottom row if the first robot moves right.
- Subtract the current element's value from
- After the loop,
ans
stores the minimum of the maximum points that the second robot can collect, given that both robots play optimally. It is the required answer.
Using this approach, we iterate through the grid only once, yielding a time complexity of O(n)
where n
is the number of columns in the grid. No additional data structures are used, so the space complexity is O(1)
as we only store a fixed number of variables.
Here's the part of the solution implementing the above steps:
s1, s2 = sum(grid[0]), 0
for j, v in enumerate(grid[0]):
s1 -= v
ans = min(ans, max(s1, s2))
s2 += grid[1][j]
return ans
In this code snippet, s1
and s2
are updated within the loop, v
is the value of the current top-row cell, and grid[1][j]
is the value at the current bottom-row cell.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through an example to illustrate the solution approach.
Consider a 2 x 3
grid matrix where the top row is [3, 1, 2]
and the bottom row is [4, 1, 5]
. We want to minimize the points that the second robot can collect, assuming both robots are playing optimally.
-
Initialization
s1
(points on the top row) =3 + 1 + 2 = 6
s2
(points on the bottom row) =0
(to start)ans
(ans to track the optimal outcome for the second robot) =infinity
-
First column iteration (
j = 0
,v = 3
)- We subtract the first robot's collected points from
s1
:s1 = 6 - 3 = 3
- The max points the second robot can have now are
max(s1, s2) = max(3, 0) = 3
- We update
ans
with the min value:ans = min(infinity, 3) = 3
- The first robot moves down, collecting points from the bottom row:
s2 = 0 + 4 = 4
- We subtract the first robot's collected points from
-
Second column iteration (
j = 1
,v = 1
)- Now
s1 = 3 - 1 = 2
- The max points the second robot can have are
max(s1, s2) = max(2, 4) = 4
- Update
ans
with the new min:ans = min(3, 4) = 3
- The first robot moves right, collecting bottom points:
s2 = 4 + 1 = 5
- Now
-
Third column iteration (
j = 2
,v = 2
)s1 = 2 - 2 = 0
- The max points are
max(s1, s2) = max(0, 5) = 5
- Update
ans
again:ans = min(3, 5) = 3
- After the first robot moves right:
s2 = 5 + 5 = 10
(this step is actually not needed as we've reached the last column)
At the completion of our loop, ans = 3
which is the optimal number of points the second robot can collect if the first robot plays optimally. Thus, the result of the given algorithm for our example would be 3
.
Solution Implementation
1class Solution:
2 def gridGame(self, grid: List[List[int]]) -> int:
3 # Initialize the answer to an infinite value since we want to minimize it later
4 min_max_score = float('inf')
5
6 # Sum of the top row's elements
7 top_sum = sum(grid[0])
8 # Initialize bottom sum to 0 since the robot hasn't moved yet
9 bottom_sum = 0
10
11 # Iterate through the elements of the top row
12 for index, value in enumerate(grid[0]):
13 # Robot moves down, so remove the current value from the top row sum
14 top_sum -= value
15 # Calculate the maximum of the remaining sums after removing the current column
16 min_max_score = min(min_max_score, max(top_sum, bottom_sum))
17 # Add the current value from the bottom row to its sum as the robot can take it
18 bottom_sum += grid[1][index]
19
20 # Return the minimum value found among the maximum sums after each possible move
21 return min_max_score
22
1class Solution {
2 public long gridGame(int[][] grid) {
3 // Initialize the answer to the maximum possible value.
4 long answer = Long.MAX_VALUE;
5 // Variables to store the sum of the top row (sumTopRow) and the sum of the bottom row (sumBottomRow).
6 long sumTopRow = 0, sumBottomRow = 0;
7
8 // Calculate the initial sum of the top row.
9 for (int value : grid[0]) {
10 sumTopRow += value;
11 }
12
13 // Find the length of the grid rows.
14 int numberOfColumns = grid[0].length;
15
16 // Iterate over every column to decide the best path.
17 for (int column = 0; column < numberOfColumns; ++column) {
18 // Subtract the current value of the top row because the robot will move right from here.
19 sumTopRow -= grid[0][column];
20 // Calculate the minimum of the maximum of the two paths (top and bottom).
21 answer = Math.min(answer, Math.max(sumTopRow, sumBottomRow));
22 // Add the current value to the sum of the bottom row as the robot can move down.
23 sumBottomRow += grid[1][column];
24 }
25 // Return the minimum result after traversing all columns.
26 return answer;
27 }
28}
29
1#include <vector>
2#include <algorithm>
3#include <climits>
4
5using ll = long long; // Define 'll' as an alias for 'long long' for simplicity
6
7class Solution {
8public:
9 long long gridGame(std::vector<std::vector<int>>& grid) {
10 // The function to calculate the minimal points the second player can obtain
11
12 ll answer = LONG_MAX; // Initialize the answer variable to maximum possible long long value
13 int numColumns = grid[0].size(); // Number of columns in the grid
14 ll upperSum = 0, lowerSum = 0; // Variables to keep track of the prefix sums of the top and bottom rows
15
16 // Calculate the initial prefix sum of the top row
17 for (int value : grid[0]) {
18 upperSum += value;
19 }
20
21 // Iterate through the grid to find the minimal points the second player will end up with
22 for (int columnIndex = 0; columnIndex < numColumns; ++columnIndex) {
23 // Decrease the upperSum by the current top grid value since the robot will pass it
24 upperSum -= grid[0][columnIndex];
25
26 // Take the maximum of the remaining values in the upperSum and lowerSum, as it's the value the second player is guaranteed to get at least
27 // Then take the minimum of this and answer to find the minimum points the second player will have to collect throughout the game
28 answer = std::min(answer, std::max(upperSum, lowerSum));
29
30 // Increase the lowerSum by the current bottom grid value as the robot can collect it
31 lowerSum += grid[1][columnIndex];
32 }
33
34 // Return the final answer which is the minimal points the second player will get
35 return answer;
36 }
37};
38
1function gridGame(grid: number[][]): number {
2 // Initialize the answer to the maximum safe integer value because we're looking for a minimum.
3 let answer = Number.MAX_SAFE_INTEGER;
4
5 // Calculate the sum of values on the top row (robot 1's path) to start with.
6 let topRowSum = grid[0].reduce((accumulator, currentValue) => accumulator + currentValue, 0);
7
8 // Initialize sum for the bottom row (robot 2's path) to be 0 since we haven't started summing it yet.
9 let bottomRowSum = 0;
10
11 // Iterate through each column.
12 for (let columnIndex = 0; columnIndex < grid[0].length; ++columnIndex) {
13 // Subtract the current top cell value as robot 1 moves right, no longer able to collect this cell's points.
14 topRowSum -= grid[0][columnIndex];
15
16 // Update the minimum answer by comparing the maximum of the two sums after robot 1 moves.
17 answer = Math.min(answer, Math.max(topRowSum, bottomRowSum));
18
19 // Add the current bottom cell value to the bottomRowSum as robot 2 moves right, since it can now collect this cell's points.
20 bottomRowSum += grid[1][columnIndex];
21 }
22
23 // Return the minimum answer which indicates the maximum points robot 2 can score when robot 1 takes the optimal path.
24 return answer;
25}
26
Time and Space Complexity
Time Complexity
The time complexity of the given code is O(n)
where n
is the number of columns in the input grid
. This is because there is a single loop that iterates through the elements of the first row of the grid. During each iteration, it performs constant-time operations: updating the summation variables s1
, s2
and computing the minimum of ans
with max(s1, s2)
.
Space Complexity
The space complexity of the given code is O(1)
. No additional data structures that grow with the size of the input are being used. The variables ans
, s1
, s2
, j
, and v
use a constant amount of space, irrespective of the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!