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
- 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.
- If robot 1 drops after column
i, then in row 0 it has already collectedgrid[0][0..i], so robot 2 (moving left along row 0) can only collectgrid[0][i+1..n-1]. - Meanwhile robot 2 collects all of
grid[1][0..i-1]in row 1, since robot 1 never visited those cells. - So robot 2's score for a drop after column
iismax(sum(grid[0][i+1..]), sum(grid[1][..i-1])), and robot 1 minimises this over alli.
💻 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 istop[n] - top[i+1], and its row-1 haul isbot[i]. - Simulating both robots move by move: O(n^2) and unnecessary, since robot 1's strategy reduces to a single choice.
- Initialising
resto 0: the minimisation needs+infas the identity.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.