598. 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:

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.

Problem Summary #

Given a matrix M of size m*n with all initial elements as 0, 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 containing two positive integers a and b, meaning that the values of all elements M[i][j] satisfying 0 <= i < a and 0 <= j < b are increased by 1. After executing the given series of operations, you need to return the number of elements containing the maximum integer in the matrix.

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 10000.

Solution Idea #

• Given an m * n matrix initially filled with 0s, and an operations array. After a series of operations, finally output the number of elements with the maximum integer in the matrix. Each operation makes all elements within a rectangle + 1.
• At first glance, this problem looks like an interval coverage problem for a segment tree, but it is actually very simple. If this problem involved arbitrary matrices, then a segment tree might be needed. In this problem, the starting point of every rectangle contains the element [0 , 0], which means every operation affects the first element. So this problem becomes very simple. After n operations, the rectangular area covered the most times must be the area where the maximum integer is located. Since the starting point is always the first element, we only need to care about the bottom-right coordinate of the rectangle. How do we calculate the bottom-right corner? We only need to dynamically maintain the minimum values of the matrix length and width each time.

Code #

package leetcode

func maxCount(m int, n int, ops [][]int) int {
	minM, minN := m, n
	for _, op := range ops {
		minM = min(minM, op[0])
		minN = min(minN, op[1])
	}
	return minM * minN
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}