2017. Grid Game
Approach
First robot splits row0 (left prefix) and row1 (right prefix); second robot takes max of remainders.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Matrix problems often involve BFS/DFS flood fill, dynamic programming on 2D grids, or spiral/diagonal traversal. For row × column DP, break it into 1D sub-problems column by column. Common pitfalls: boundary checks and modifying the input matrix in-place.
Simulation problems require implementing the described process step by step. Focus on correctly handling edge cases and state transitions. Common in geometry, game problems, and string manipulation. Optimize only if the naive simulation exceeds the time limit.
// Approach: First robot splits row0 (left prefix) and row1 (right prefix); second robot takes max of remainders.
// Time: O(n) Space: O(1)
public class Solution
{
public long GridGame(int[][] grid)
{
int n = grid[0].Length;
long ans = long.MaxValue;
long sumRow0 = 0;
for (int i = 0; i < n; i++)
sumRow0 += grid[0][i];
long sumRow1 = 0;
for (int i = 0; i < n; ++i)
{
sumRow0 -= grid[0][i];
ans = Math.Min(ans, Math.Max(sumRow0, sumRow1));
sumRow1 += grid[1][i];
}
return ans;
}
}