This is the sixth day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

598. Scope sum II

Given a matrix M of size m by n with zero initial elements and a series of update operations on m.

The operations are represented by a two-dimensional array, where each operation is represented by an array of two positive integers A and b. The implication is to increment the value of all elements M[I][j] that match 0 <= I < a and 0 <= j < b by one.

After performing a given set of operations, you need to return the number of elements in the matrix that contain the largest integer.

Example 1: input: m = 3, n = 3 operations = [[2,2],[3,3]] output: 4 Initial state, M = [[0, 0, 0], [0, 0, 0], [0, 0, 0]] execute after the operation (2, 2], M = [[1, 1, 0], [1, 1, 0], [0, 0, 0]] after [3, 3] after the operation, M = [[2, 2, 1], [2, 2, 1], [1, 1]] The largest integer in M is 2, and there are four elements in M with the value of 2. So return 4.Copy the code

Note:

  • The range of m and n is [1,40000].
  • The range of A is [1,m], and the range of B is [1,n].
  • The number of operations does not exceed 10,000.

Their thinking

Because each operation increases the value of all elements M[I][j] that match 0 <= I < a and 0 <= j < b by 1.

Therefore, for each operation we can as a coating on the basis of the original matrix M matrix, and all the coverage matrix from the original matrix are covered, and the number of elements in the matrix contains the largest integer, may be regarded as that part of the matrix M are covered most times, therefore, we only need to remove each operation in the smallest positive integer a and b, That’s the part that’s covered the most, and their area is equal to the number of elements in the largest integer.

code

class Solution {
public:
    int maxCount(int m, int n, vector<vector<int>>& ops) {
        if (ops.size() = =0) return m*n;
        int l(0x7fffffff).r(0x7fffffff);
        for (auto  op:ops)
        {
            l=min(op[0],l);
            r=min(op[1],r);
        }
        returnl*r; }};Copy the code

Complexity analysis

  • Time complexity: O(k), where k is the length of the array ops\textit{ops}ops.
  • Space complexity: O(1).