2017. Grid Game

MediumArrayMatrixPrefix Sum
Leetcode Link

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:

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

  1. The second robot could take the maximum points from the top row after the first robot completes its path.
  2. 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:

  1. 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).
  2. Initialize s2 to 0 as the second robot starts from the first column and has not collected any points yet.
  3. Initialize ans to inf 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.
  4. 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 and s2. 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.
  5. 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 Evaluator

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

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

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

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

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings

Prefix Sum

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: The Smart, Data-Driven Way to Prepare for Tech Interviews

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 Review

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!