598. Range Addition II


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:

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.

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.


Solution

Approach #1 Brute Force [Time Limit Exceeded]

The simplest method is to create a actual 2-D array of size x(), perform all the operations one by one on the given range of elements, and then count the number of maximum elements. Now, we know that all the operations performed always include the element at index . Thus, the element will always be the maximum. After performing all the operations, we can count the number of elements equal to to get the required count of the maximum elements.

Complexity Analysis

  • Time complexity : . Array is updated times, where represents number of times operation is preformed i.e. .

  • Space complexity : . Array of size is used.

Approach #2 Single Pass [Accepted]

Algorithm

As per the given problem statement, all the operations are performed on a rectangular sub-matrix of the initial all 0's matrix. The upper left corner of each such rectangle is given by the index and the lower right corner for an operation is given by the index .

The maximum element will be the one on which all the operations have been performed. The figure below shows an example of two operations being performed on the initial array.

Range_Addition

From this figure, we can observe that the maximum elements will be the ones which lie in the intersection region of the rectangles representing the operations. Further, we can observe that to count the number of elements lying in this intersection region, we don't actually need to perform the operations, but we need to determine the lower right cornerof the intersecting region only. This corner is given by , where reprsents the minimum value of from among all the 's in the given set of operations.

Thus, the resultant count of elements lying in the intersection is given by: x.

Complexity Analysis

  • Time complexity : . Single traversal of all operations is done. refers to the number of operations.

  • Space complexity : . No extra space is used.

Analysis written by: @vinod23

Submit Solution