Grid game

Array Matrix Prefix Sum

60.9% acceptance

Feb 25, 2026

1807

You are given a 0-indexed 2D array grid of size 2 x n. Two robots start at (0,0) and want to reach (1, n-1). First robot moves and collects points (setting them to 0). Second robot then moves optimally to maximize its collection. First robot wants to minimize what the second robot can collect. Return the number of points collected by the second robot.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn grid_game(grid: Vec<Vec<i32>>) -> i64 {
    let n = grid[0].len();
    // First robot makes exactly one downward move at column i.
    // It collects: grid[0][0..=i] + grid[1][i..n-1]
    // After that, second robot can collect either:
    //   - top row right part: sum(grid[0][i+1..n])
    //   - bottom row left part: sum(grid[1][0..i])
    // Second robot picks max of these two. First robot minimizes this max.
    
    let top_sum: i64 = grid[0].iter().map(|&x| x as i64).sum();
    let mut top_prefix = 0i64;
    let mut bot_prefix = 0i64;
    let mut ans = i64::MAX;
    
    for i in 0..n {
      top_prefix += grid[0][i] as i64;
      let top_right = top_sum - top_prefix;
      let second_best = top_right.max(bot_prefix);
      ans = ans.min(second_best);
      bot_prefix += grid[1][i] as i64;
    }
    ans
  }
}