Range Addition II

Problem

You are given an m x n matrix M initialized with all 0’s and an array of operations ops, where ops[i] = [ai, bi] means M[x][y] should be incremented by one for all 0 <= x < ai and 0 <= y < bi.

Count and return the number of maximum integers in the matrix after performing all the operations.

Constraints

• 1 <= m, n <= 4 * 104
• 0 <= ops.length <= 104
• ops[i].length == 2
• 1 <= ai <= m
• 1 <= bi <= n

Solution

The problem Range Addition II can be solved by checking minimum values for ai and bi. Since each operation increments each elements starting from 0, M[xi][y] >= M[xj][y] and M[x][yi] >= M[x][yj] holds true for i < j. This also implies that once an area is excluded from the operation, it is impossible for elements in the area to contain maximum integers. Therefore, the number of maximum integers in the matrix can be found with a single iteration of given operations.

Implementation

class Solution
{
  public:
    int maxCount(int m, int n, vector<vector<int>> &ops)
    {
        for (vector<int> op : ops)
        {
            m = min(m, op[0]);
            n = min(n, op[1]);
        }

        return m * n;
    }
};