Range Addition II

• LeetCode: Range Addition II

• Problem:

Given an m * n matrix M initialized with all 0's and several update operations.

Operations are represented by a 2D array, and each operation is represented by an array with two positive integers a and b, which means M[i][j] should be added by one for all 0 <= i < a and 0 <= j < b.

You need to count and return the number of maximum integers in the matrix after performing all the operations.

Example 1:

• Note:

1. The range of m and n is [1,40000].

2. The range of a is [1,m], and the range of b is [1,n].

3.The range of operations size won't exceed 10,000.

• Examples:

Input: 
m = 3, n = 3
operations = [[2,2],[3,3]]
Output: 4
Explanation: 
Initially, M = 
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

After performing [2,2], M = 
[[1, 1, 0],
 [1, 1, 0],
 [0, 0, 0]]

After performing [3,3], M = 
[[2, 2, 1],
 [2, 2, 1],
 [1, 1, 1]]

So the maximum integer in M is 2, and there are four of it in M. So return 4.

• Analysis:

For operations[a, b] matrix, the [a, b] means matrix[0 - a][0 - b] to add by 1.

As a result, we calculate the frequency of each  a and b and sort in ascending order. 

Finally, we sum from rear to front and find the cursors.

• Code - Java:

class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        int[] row = new int[m];
        int[] col = new int[n];
        int len = ops.length;
        for (int i = 0; i < len; i++) {
            row[(ops[i][0] - 1)] += 1;
            col[(ops[i][1] - 1)] += 1;
        }
        int maxRow = m - 1;
        int maxCol = n - 1;
        for (int i = m - 2; i >= 0; i--) {
            row[i] += row[i + 1];
            if (row[i] > row[i + 1]) {
                maxRow = i;
            }    
        }
        for (int i = n - 2; i >= 0; i--) {
            col[i] += col[i + 1];
            if (col[i] > col[i + 1]) {
                maxCol = i;
            }
        }
        return (maxRow + 1) * (maxCol + 1);
    }
}

• Code - C++:

class Solution {
public:
    int maxCount(int m, int n, vector<vector<int>>& ops) {
        vector<int> row(m, 0);
        vector<int> col(n, 0);
        for (int i = 0; i < ops.size(); i++) {
            row[(ops[i][0] - 1)] += 1;
            col[(ops[i][1] - 1)] += 1;
        }
        int maxRow = m - 1;
        int maxCol = n - 1;
        for (int i = m - 2; i >= 0; i--) {
            row[i] += row[i + 1];
            if (row[i] > row[i + 1]) {
                maxRow = i;
            }    
        }
        for (int i = n - 2; i >= 0; i--) {
            col[i] += col[i + 1];
            if (col[i] > col[i + 1]) {
                maxCol = i;
            }
        }
        return (maxRow + 1) * (maxCol + 1);
    }
};

• Code - Python:

class Solution(object):
    def maxCount(self, m, n, ops):
        """
        :type m: int
        :type n: int
        :type ops: List[List[int]]
        :rtype: int
        """
        row = [0 for i in range(m)]
        col = [0 for j in range(n)]
        for i in range (len(ops)):
            row[(ops[i][0] - 1)] += 1
            col[(ops[i][1] - 1)] += 1;
        maxRow, maxCol = m - 1, n - 1
        for i in range(m - 2, -1, -1):
            row[i] += row[i + 1];
            if (row[i] > row[i + 1]):
                maxRow = i
        for i in range(n - 2, -1, -1):
            col[i] += col[i + 1];
            if col[i] > col[i + 1]:
                maxCol = i
        return (maxRow + 1) * (maxCol + 1)

• Time Complexity: O(M + N)
• Space Complexity: O(M + N)