We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Grid Game

Number: 2145

Difficulty: Medium

Paid? No

Companies: Google, T System

Problem Description

Given a 2 x n grid where grid[r][c] indicates the points at cell (r, c), two robots start at (0,0) and must reach (1, n-1) moving only right or down. The first robot collects points along its chosen path and sets those cells to 0. The second robot then collects points along its path. The first robot’s goal is to minimize the points collected by the second robot, while the second robot aims to maximize them. Under optimal play from both, determine the final points collected by the second robot.

Key Insights

  • The first robot’s only decision is when to move down from the top row to the bottom row.
  • When the first robot moves down at a particular column j, the second robot’s maximum attainable score is determined by:
    • The points remaining in the top row to the right of j.
    • The points remaining in the bottom row to the left of j.
  • For each possible down move column j, the score for the second robot equals the maximum of the top row sum (from j+1 to n-1) and the bottom row sum (from 0 to j-1).
  • The optimal strategy for the first robot is to choose the column j that minimizes this maximum value.

Space and Time Complexity

Time Complexity: O(n) – We iterate over the columns once to compute prefix/suffix sums and once more to determine the optimal move. Space Complexity: O(n) – For storing prefix and suffix sums (which can be optimized to O(1) with careful handling).

Solution

We can precompute two arrays:

  1. A suffix sum for the top row where for each column i, suffix_top[i] = sum(grid[0][i] ... grid[0][n-1]).
  2. A prefix sum for the bottom row where for each column i, prefix_bottom[i] = sum(grid[1][0] ... grid[1][i]). For each possible column j where the first robot goes down, the score the second robot obtains is the maximum of:
  • The remaining sum in the top row (i.e., suffix_top[j+1] if j+1 < n, else 0).
  • The collected bottom row sum before j (i.e., prefix_bottom[j-1] if j-1 >= 0, else 0). We iterate all possible j and choose the minimum among these maximum values. This gives the score of the second robot under optimal play.

Code Solutions

# Python solution for Grid Game

def gridGame(grid):
    n = len(grid[0])
    
    # Precompute suffix sum for the top row
    suffix_top = [0] * n
    suffix_top[n-1] = grid[0][n-1]
    for i in range(n-2, -1, -1):
        suffix_top[i] = grid[0][i] + suffix_top[i+1]
        
    # Precompute prefix sum for the bottom row
    prefix_bottom = [0] * n
    prefix_bottom[0] = grid[1][0]
    for i in range(1, n):
        prefix_bottom[i] = grid[1][i] + prefix_bottom[i-1]
    
    # Initialize minimum score with a large number
    min_score = float('inf')
    
    # Consider all possible positions to go down (column index j)
    for j in range(n):
        # Points left from top row after j
        top_remaining = suffix_top[j+1] if j+1 < n else 0
        # Points collected from bottom row before j
        bottom_collected = prefix_bottom[j-1] if j-1 >= 0 else 0
        
        # The score for the second robot is the maximum of these two
        score = max(top_remaining, bottom_collected)
        min_score = min(min_score, score)
        
    return min_score

# Example test cases
if __name__ == "__main__":
    grid1 = [[2,5,4],[1,5,1]]
    grid2 = [[3,3,1],[8,5,2]]
    grid3 = [[1,3,1,15],[1,3,3,1]]
    print(gridGame(grid1))  # Expected output: 4
    print(gridGame(grid2))  # Expected output: 4
    print(gridGame(grid3))  # Expected output: 7
← Back to All Questions