CareerCup

import java.util.Scanner;

public class Main {

    /*
    * Input: n and m
    *        then nxm matrix.
    *
    * ex: 3 4
    *     1 2 2 2
    *     2 2 2 1
    *     1 2 2 2
    * */

    private int n;
    private int m;
    private int[][] grid;
    private int[][] needsProcessing;

    int[] upperLeftmostPoint;
    int[] lowerRightmostPoint;

    public void init(){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        while(n <= 0 || m <= 0) {
            System.out.println("Insert valid n and m values");
            n = sc.nextInt();
            m = sc.nextInt();
        }
        grid = new int[n][m];
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                grid[i][j] = sc.nextInt();
            }
        }
        sc.close();

        /* process method will determine which cells do not need processing
        * in order to prevent repeating some operations and we will use needsProcessing for that.
        * */
        needsProcessing = new int[n][m];
        for(int i = 0 ; i < n ; i ++){
            for(int j = 0; j < m ; j ++){
                needsProcessing[i][j] = 0;
            }
        }

        /*Initially we assume cell at (0,0) as a submatrix is the result.*/
        upperLeftmostPoint = new int[2];
        lowerRightmostPoint = new int[2];
        upperLeftmostPoint[0] = 0;
        upperLeftmostPoint[1] = 0;
        lowerRightmostPoint[0] = 0;
        lowerRightmostPoint[1] = 0;
    }

    public void print(){
        System.out.println("Upper leftmost:   ( " + (upperLeftmostPoint[0] + 1) + " , " + (upperLeftmostPoint[1] + 1) + " )");
        System.out.println("Bottom rightmost: ( " + (lowerRightmostPoint[0] + 1) + " , " + (lowerRightmostPoint[1] + 1) + " )");

        for(int i = upperLeftmostPoint[0] ; i <= lowerRightmostPoint[0] ; i ++){
            for(int j = upperLeftmostPoint[1] ; j <= lowerRightmostPoint[1] ; j ++){
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        }
    }

    /*
    * We iterate through each cell in the matrix.
    * First, k is computed. If current cell's value is x, then k is the count of continuous
    * x's below the current cell including x.
    * Then we hold the "horizontals" array of k elements. Each of them represents the number of continous x's
    * rightwards.
    * ex: In matrix
    *      2 2 1
    *      2 2 2
    *      2 1 1
    *      1 2 2
    *      2 3 1
    *  If current cell is the first cell which has the value 2. Then k is 3 and
    *  horizontals array is {2, 3, 1}.
    *
    *  Then we compute the biggest submatrix assuming upper leftmost cell is the current cell
    *  using horizontals array. For example, here in the same example we first look at the
    *  horizontals[0]. Take 2 2 as the biggest sub matrix so far. Then look at the second element
    *  of the horizontals. We see that 2 2 is bigger and so on.
    *                                  2 2
    *  After processing the current cell at the end we compare what we found with the current cell to
    *  maxSoFar. Then we update the needed parameters. Also in order to prevent repeating we use needsProcessing
    *  matrix. We do that by checking the minimum values. If horizontal[minValueIndexSoFar] >= horizontal[y] then we won't need to
    *  process grid[i + y][j] because grid[i][j] will have done the needed operations and process method will repeat some operations
    *  while processing grid[i+y][j].
    * */

    public void process(){
        int maxSoFar = (upperLeftmostPoint[0] - upperLeftmostPoint[1] + 1)*(lowerRightmostPoint[0] - lowerRightmostPoint[1] + 1);
        for(int i = 0 ; i < n ; i ++){
            for(int j = 0; j < m ; j ++) {
                if (needsProcessing[i][j] == 0){
                    int k = 0;
                    while (k + i < n && grid[i][j] == grid[k + i][j]) k++;

                    int[] horizontals = new int[k];

                    for (int s = 0; s < k; s++) {
                        int t = 0;
                        while (t + j < m && grid[i + s][j] == grid[i + s][t + j]) t++;
                        horizontals[s] = t;
                    }

                    int minValueIndexSoFar = 0;
                    int maxOfCurrentSoFar = horizontals[0];
                    int maxAreaLowerRightmostIndexY = 0;
                    for (int s = 0; s < k; s++) {
                        if (horizontals[minValueIndexSoFar] >= horizontals[s]) {
                            minValueIndexSoFar = s;
                            /*This means processing grid[i+s][j] is not necessary.*/
                            needsProcessing[i+s][j] = 1;
                        }
                        if (maxOfCurrentSoFar < (s + 1) * horizontals[minValueIndexSoFar]) {
                            maxOfCurrentSoFar = (s + 1) * horizontals[minValueIndexSoFar];
                            maxAreaLowerRightmostIndexY = s;
                        }
                    }
                    if (maxOfCurrentSoFar > maxSoFar) {
                        maxSoFar = maxOfCurrentSoFar;
                        upperLeftmostPoint[0] = i;
                        upperLeftmostPoint[1] = j;
                        lowerRightmostPoint[0] = i + maxAreaLowerRightmostIndexY;
                        lowerRightmostPoint[1] = j + maxOfCurrentSoFar / (maxAreaLowerRightmostIndexY + 1) - 1;
                    }
                }
            }
        }
    }

    public void run(){
        init();
        process();
        print();
    }

    public static void main(String[] args) {
        new Main().run();
    }
}