Minimizing Robot's Maximum Collectable Values In Grid Game
Minimax algorithm for grid game: TC O(n), SC O(n). Robot 1 tries to minimize values collected by Robot 2, who maximizes. Prefix sums used to optimize calculations.
Problem
TC: O(n)
SC: O(n)
class Solution {
public long gridGame(int[][] grid) {
long prefix1[] = new long[grid[0].length];
long prefix2[] = new long[grid[0].length];
long sum =0;
for(int i=0;i<grid[0].length;i++){
sum+=grid[0][i];
prefix1[i]= sum;
}
sum =0;
for(int i=0;i<grid[0].length;i++){
sum+=grid[1][i];
prefix2[i]= sum;
}
long res = Long.MAX_VALUE;
for(int i=0;i<grid[0].length;i++){
//if robot 1 at 2 cross at index i
//in this row...