Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 == 2n == grid[r].length1 <= n <= 5 * 1041 <= grid[r][c] <= 105Problem summary: 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
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array
[[2,5,4],[1,5,1]]
[[3,3,1],[8,5,2]]
[[1,3,1,15],[1,3,3,1]]
minimum-penalty-for-a-shop)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2017: Grid Game
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;
}
}
// Accepted solution for LeetCode #2017: Grid Game
func gridGame(grid [][]int) int64 {
ans := math.MaxInt64
s1, s2 := 0, 0
for _, v := range grid[0] {
s1 += v
}
for j, v := range grid[0] {
s1 -= v
ans = min(ans, max(s1, s2))
s2 += grid[1][j]
}
return int64(ans)
}
# Accepted solution for LeetCode #2017: Grid Game
class Solution:
def gridGame(self, grid: List[List[int]]) -> int:
ans = inf
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
// Accepted solution for LeetCode #2017: Grid Game
impl Solution {
pub fn grid_game(grid: Vec<Vec<i32>>) -> i64 {
let n = grid[0].len();
let mut memo1 = vec![0;n+1];
let mut memo2 = vec![0;n+1];
for i in 0..n {
memo1[i+1] = memo1[i] + grid[0][i] as i64;
memo2[i+1] = memo2[i] + grid[1][i] as i64;
}
let mut result = i64::max_value();
for i in 0..n {
result = result.min(memo2[i].max(memo1[n] - memo1[i+1]));
}
result
}
}
// Accepted solution for LeetCode #2017: Grid Game
function gridGame(grid: number[][]): number {
let ans = Number.MAX_SAFE_INTEGER;
let s1 = grid[0].reduce((a, b) => a + b, 0);
let s2 = 0;
for (let j = 0; j < grid[0].length; ++j) {
s1 -= grid[0][j];
ans = Math.min(ans, Math.max(s1, s2));
s2 += grid[1][j];
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.