Google India | L5 Onsite Interview Question

Three players, A, B, and C play an online game. 
The game consists of a map in the shape of an RxC grid.
Each player has to capture one or more cells in the RxC grid. 
So, after the game, each cell would have the name of the player who captured it.

The winner of the game will be the player who covers the largest rectangle area in the RxC grid. 
Find the area of that largest rectangle.
  
Example:

+---+---+---+---+
| B | A | A | C |
+---+---+---+---+
| B | A | A | B |
+---+---+---+---+
| C | C | A | A |
+---+---+---+---+
| B | B | C | C |
+---+---+---+---+
  
In the above 4x4 grid, the size of the largest rectangle is 4 and the corresponding winner would be A.
  
  
  size? = 1000x1000 
  cellsFilled? = true
  there can be more players.
  no.of players as List<String>
  no more than 50 players
  
  String board[][];
  List<String> player;
  
p = no. of players
rxc = rows and column

O(p x (rxc + (r * r)))
 O(p * r*c)

+---+---+---+---+
| 0 | 1 | 1 | C |
+---+---+---+---+
| 0 | 1 | 1 | B |
+---+---+---+---+
| 0 | 0 | 1 | A |
+---+---+---+---+
| 0 | B | C | C |

  
  iterating for player A
+---+---+---+---+
| 0 | 1 | 1 | 0 |
+---+---+---+---+
| 0 | 2 | 2 | 0 |
+---+---+---+---+
| 0 | 0 | 3 | 0 |
+---+---+---+---+
| 0 | 0 | 0 | 0 |
  
    
String getWinner(List<String> players, String[][] board) {
        String winner = "";
        int max = 0;
        for(String p: players) {
            int maxRectangleForPlayer = getMaxRectangleSize(board, p);
            if(maxRectangleForPlayer > max){
                max = maxRectangleForPlayer;
                winner = p;
            }
        }

        return winner;
    }

// getMaxRectangleSize & getRectangleSize are slight modification of https://leetcode.com/problems/largest-rectangle-in-histogram/description/
    int getMaxRectangleSize(String[][] board, String player) {
        int[][] heights = new int[board.length][board[0].length];
        //come back to merge these loops
        for(int r = 0; r < board.length; r++){
            if(board[r][0].equals(player)) {
                heights[r][0] = 1;
            }
        }

        for(int r = 1; r < board.length; r++){
            for(int c = 0; c < board[0].length; c++){
                if(board[r][c].equals(player)) {
                    heights[r][c] = heights[r - 1][c] + 1;
                }
            }
        }

        //
        int max = 0;
        for(int r = 0; r < board.length; r++){
            //rectangle size if I take height as heights[r][c]
            int rectangleSize = getRectangleSize(heights, r);
            max = Math.max(max, rectangleSize);
        }
        return max;
    }

     int getRectangleSize(int[][] heights, int r) {

        int[] row = heights[r];
        int[] leftBoundary = new int[row.length];
        leftBoundary[0] = -1;
        for(int c = 1; c < row.length; c++) {
            int prev = c - 1;
            while(prev >= 0 && row[c] >= row[prev]) {
                prev = leftBoundary[prev];
            }

            leftBoundary[c] = prev;
        }
        int[] rightBoundary = new int[row.length];
        rightBoundary[rightBoundary.length - 1] = heights.length;
        for(int c = row.length - 2; c >= 0; c--) {
            int next = c + 1;
            while(next < row.length && row[c] >= row[next]) {
                next = rightBoundary[next];
            }

            rightBoundary[c] = next;
        }

        int max = 0;
        for(int c = 0; c < row.length; c++) {
            int currRectangleArea = row[c] * (rightBoundary[c] - leftBoundary[c] - 1);
            max = Math.max(max, currRectangleArea);
        }
        return max;
    }