Range Addition II
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.
Example 1:
Input: m = 3, n = 3, ops = [[2,2],[3,3]]
Output: 4
Explanation: The maximum integer in M is 2, and there are four of it in M. So return 4.
Example 2:
Input: m = 3, n = 3, ops = [[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3]]
Output: 4
Example 3:
Input: m = 3, n = 3, ops = []
Output: 9
Solution: Track smallest
naive solution: fill all of matrix n * m
Improved solution: fill only top row and left column
Improved solution 2: track only smallest
func maxCount(m int, n int, ops [][]int) int {
x := m
y := n
for _,pair := range ops {
x = min(pair[0], x)
y = min(pair[1], y)
}
return x * y
}
func min(i int, j int) int{
if i >= j {
return j
} else {
return i
}
}
TC: O(N)
SC: O(1)
Last updated
Was this helpful?