⚡Flashcard Drill➔
NeetCode #119LC-2017MediumArrays & Hashing
← Back to All Problems

#119 · #2017 · Grid Game(网格游戏)

📌 Problem Statement & Constraints

Two robots play on a 2 x n grid. Robot 1 starts at (0, 0) and moves only right; it may drop to row 1 at any column, after which it continues right and cannot return. Robot 2 starts at (1, n-1) and moves only left, also able to switch rows once. Cells collected by robot 1 become zero for robot 2. Robot 1 plays to minimise robot 2's score. Return robot 2's final score. Constraints: 1 <= n <= 5 * 10^4, 0 <= grid[i][j] <= 10^5.

💡 Core Algorithmic Approaches

  1. Robot 1's only decision is the column at which it drops from row 0 to row 1. Enumerate that choice implicitly with prefix sums.
  2. If robot 1 drops after column i, then in row 0 it has already collected grid[0][0..i], so robot 2 (moving left along row 0) can only collect grid[0][i+1..n-1].
  3. Meanwhile robot 2 collects all of grid[1][0..i-1] in row 1, since robot 1 never visited those cells.
  4. So robot 2's score for a drop after column i is max(sum(grid[0][i+1..]), sum(grid[1][..i-1])), and robot 1 minimises this over all i.

💻 Benchmark Python3 Implementation

class Solution:
    def gridGame(self, grid: List[List[int]]) -> int:
        n = len(grid[0])
        top = [0] * (n + 1)                # prefix sums for row 0
        bot = [0] * (n + 1)                # prefix sums for row 1
        for i in range(n):
            top[i + 1] = top[i] + grid[0][i]
            bot[i + 1] = bot[i] + grid[1][i]
        res = float("inf")
        for i in range(n):
            # robot 1 drops after column i; robot 2 takes the better of the two remainders
            r2 = max(top[n] - top[i + 1], bot[i])
            res = min(res, r2)             # robot 1 minimises robot 2's score
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): prefix sums plus one pass over the candidate drop columns.
💾 Space Complexity
O(n) for the two prefix arrays (O(1) if computed on the fly).

⚠️ Interview Pitfalls & Follow-ups

  • Assuming robot 1 should maximise its own score: the problem states robot 1 plays to minimise robot 2's score, which is a different objective.
  • Getting the prefix indices wrong: after dropping past column i, robot 2's row-0 haul is top[n] - top[i+1], and its row-1 haul is bot[i].
  • Simulating both robots move by move: O(n^2) and unnecessary, since robot 1's strategy reduces to a single choice.
  • Initialising res to 0: the minimisation needs +inf as the identity.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems