# Easy to Understand Java Solution

• 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;
}
}
``````

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