Easy to Understand Java Solution


  • 0

    The key insight to this problem is that the sub-matrix that contains the maximum integers will, after every operation, either stay the same size or shrink down. I use variables x and y to denote the sub-matrix that contains all of the maximum integers. I.e., if

    1, 1, 0
    1, 1, 0
    0, 0, 0

    were our matrix, then x = 2 and y = 2. I found it useful to think through this problem by thinking about what would happen if we had 0 operations, what would happen if we had 1 operations, then 1+ operations.

    0 operations: If we have 0 operations, then the matrix is full of zeros, and thus, all of the zeros are our max numbers, and we have a matrix full of max numbers. Return m * n.

    1 operation: If we have 1 operation: [a1, b1], then the submatrix that this 1 operation is applied to becomes the submatrix that contains all of the 1's, which is our max number, since every other number will be 0. Return a1 * b1.

    1+ operations: Extending what we learned from the 1 operation case, what happens if we have 2 operations? Let's say our second operation is [a2, b2] There are four cases for the 2nd operation to be.

    Case 1: a2 >= a1 and b2 >= b1
    In this case the submatrix of our max numbers stays the same. We know this because the operation [a2, b2] will increment every number in our submatrix of maxes as well as more numbers. So relatively our submatrix of maxes will still be the maxes. We keep x and y the same.

    Case 2: a2 >= a1 and b2 < b1
    In this case, the submatrix of our max numbers does not stay the same. Since b2 < b1, we know that only a submatrix of our current submatrix of maxes will be incremented. Thus, we know that we must take a submatrix from our submatrix to be our new submatrix of maxes. We don't make any modifications to x since a2 >= a1, but we set y = b2.

    Case 3: a2 < a1 and b2 >= b1
    Similar logic as case 2. No modifications to y, and set x = a2.

    Case 4: a2 < a1 and b2 < b1
    Similar logic as case 2. Set x = a2 and y = b2.

    class Solution {
        public int maxCount(int m, int n, int[][] ops) {
            if(ops.length == 0) return m * n;
            int x = -1;
            int y = -1;
            for(int[] op: ops) {
                int a = op[0];
                int b = op[1];
                
                // will only set on the first iteration
                x = (x == -1) ? a : x;
                y = (y == -1) ? b : y;
                
                if(a < x) x = a;
                if(b < y) y = b;
            }
            return x * y;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.