In this guide, you will get 598. Range Addition II LeetCode Solution with the best time and space complexity. The solution to Range Addition II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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
Constraints:
1 <= m, n <= 4 * 104
0 <= ops.length <= 104
ops[i].length == 2
1 <= ai <= m
1 <= bi <= n
Complexity Analysis
Time Complexity: O(N), where N = |\texttt{ops}|
Space Complexity:
598. Range Addition II LeetCode Solution in C++
class Solution {
public:
int maxCount(int m, int n, vector<vector<int>>& ops) {
int minY = m;
int minX = n;
for (const vector<int>& op : ops) {
minY = min(minY, op[0]);
minX = min(minX, op[1]);
}
return minX * minY;
}
}; /* code provided by PROGIEZ */
598. Range Addition II LeetCode Solution in Java
class Solution {
public int maxCount(int m, int n, int[][] ops) {
int minY = m;
int minX = n;
for (int[] op : ops) {
minY = Math.min(minY, op[0]);
minX = Math.min(minX, op[1]);
}
return minX * minY;
}
} // code provided by PROGIEZ
598. Range Addition II LeetCode Solution in Python
class Solution:
def maxCount(self, m: int, n: int, ops: list[list[int]]) -> int:
minY = m
minX = n
for y, x in ops:
minY = min(minY, y)
minX = min(minX, x)
return minX * minY # code by PROGIEZ
