Grid Game - Practice Coding Problems

Grid Game - Problem

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 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.

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.

Input & Output

Example 1 — Basic Grid

$ Input: grid = [[2,5,4],[8,10,3]]

› Output: 4

💡 Note: The first robot goes down at position 1, taking path (0,0)→(0,1)→(1,1)→(1,2), collecting 2+5+10+3=20 points. The second robot chooses the top path to collect 0+0+4=4 points.

Example 2 — Better Bottom Path

$ Input: grid = [[1,3,1,15],[1,3,3,1]]

› Output: 7

💡 Note: The first robot goes down at position 2, collecting 1+3+1+3+1=9 points. The remaining points allow the second robot to collect max(0+0+15, 1+3+0) = max(15,4) = 15. But the optimal first robot strategy gives second robot only 7.

Example 3 — Equal Rows

$ Input: grid = [[1,1,1],[1,1,1]]

› Output: 1

💡 Note: With identical rows, the first robot can force the second robot to get at most 1 point regardless of strategy.

Constraints

grid.length == 2
n == grid[r].length
1 ≤ n ≤ 5 × 10⁴
1 ≤ grid[r][c] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Initial Grid

2×n grid with point values, both robots start at (0,0)

First Robot Move

First robot chooses path to minimize second robot's score

Second Robot Move

Second robot takes optimal path on remaining points

Key Takeaway

🎯 Key Insight: The first robot must choose a path that minimizes the second robot's maximum possible score

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that the first robot must go down exactly once, creating two segments. The optimal strategy uses prefix sums to efficiently evaluate each possible down position. Best approach: Prefix Sum - Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Path Enumeration	O(2^n)	O(n)	Try all possible paths for the first robot and calculate second robot's optimal score
Prefix Sum Optimization	O(n)	O(1)	Use prefix sums to efficiently calculate remaining points after first robot's path

Brute Force Path Enumeration — Algorithm Steps

Generate all valid paths for first robot
For each path, simulate point collection and grid clearing
Find optimal path for second robot on remaining grid
Return minimum of all second robot scores

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Paths

Find all valid paths from (0,0) to (1,n-1)

Simulate Each

For each path, clear those cells and find second robot's best score

Find Minimum

Return the minimum second robot score across all paths

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_N 100
#define MAX_PATHS 1000

int n;
int paths[MAX_PATHS][MAX_N][2];
int pathLengths[MAX_PATHS];
int numPaths = 0;

void generatePaths(int r, int c, int currentPath[][2], int pathLen) {
    currentPath[pathLen][0] = r;
    currentPath[pathLen][1] = c;
    pathLen++;
    
    if (r == 1 && c == n - 1) {
        for (int i = 0; i < pathLen; i++) {
            paths[numPaths][i][0] = currentPath[i][0];
            paths[numPaths][i][1] = currentPath[i][1];
        }
        pathLengths[numPaths] = pathLen;
        numPaths++;
        return;
    }
    
    if (r < 1) {
        generatePaths(r + 1, c, currentPath, pathLen);
    }
    if (c < n - 1) {
        generatePaths(r, c + 1, currentPath, pathLen);
    }
}

int findMaxPath(int grid[2][MAX_N], int r, int c) {
    if (r == 1 && c == n - 1) {
        return grid[r][c];
    }
    
    int maxScore = 0;
    if (r < 1) {
        int score = findMaxPath(grid, r + 1, c);
        if (score > maxScore) maxScore = score;
    }
    if (c < n - 1) {
        int score = findMaxPath(grid, r, c + 1);
        if (score > maxScore) maxScore = score;
    }
    
    return grid[r][c] + maxScore;
}

int solution(int grid[2][MAX_N]) {
    int currentPath[MAX_N][2];
    numPaths = 0;
    generatePaths(0, 0, currentPath, 0);
    
    int minSecondScore = INT_MAX;
    
    for (int i = 0; i < numPaths; i++) {
        int gridCopy[2][MAX_N];
        for (int r = 0; r < 2; r++) {
            for (int c = 0; c < n; c++) {
                gridCopy[r][c] = grid[r][c];
            }
        }
        
        for (int j = 0; j < pathLengths[i]; j++) {
            int r = paths[i][j][0];
            int c = paths[i][j][1];
            gridCopy[r][c] = 0;
        }
        
        int secondScore = findMaxPath(gridCopy, 0, 0);
        if (secondScore < minSecondScore) {
            minSecondScore = secondScore;
        }
    }
    
    return minSecondScore;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int grid[2][MAX_N];
    char *ptr = strchr(line, '[') + 1;
    
    for (int i = 0; i < 2; i++) {
        ptr = strchr(ptr, '[') + 1;
        int j = 0;
        char *token = strtok(ptr, ",]");
        while (token && j < MAX_N) {
            grid[i][j] = atoi(token);
            j++;
            if (i == 0) n = j;
            token = strtok(NULL, ",]");
            if (token && token[0] == ']') break;
        }
        ptr = strchr(ptr, ']') + 1;
    }
    
    printf("%d\n", solution(grid));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

There are exponentially many paths from (0,0) to (1,n-1) to enumerate

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth and path storage

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Path Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler