[leetcode #598] Range Addition II

Problem

You are given an m x n matrix M initialized with all 0's and an array of operations ops, where ops[i] = [aᵢ, bᵢ] means M[x][y] should be incremented by one for all 0 <= x < aᵢ and 0 <= y < bᵢ.

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 * 10⁴
・ 1 <= ops.length <= 10⁴
・ ops[i].length == 2
・ 1 <= aᵢ <= m
・ 1 <= bᵢ <= n

Idea

복잡하게 생각하지 말고 간단하게 생각하면 쉽게 풀 수 있는 문제다. x와 y값을 가진 ops array를 탐색하면서 x와 y의 최소값을 찾기만 하면 된다. x와 y의 최소값에 해당하는 영역이 가장 많이 값이 올라가는 영역이기 때문이다.

알고리즘은 다음과 같다.

1. ops array를 탐색하면서 x값과 y값의 최소값을 찾는다.
2. x의 최소값과 y의 최소값의 곱을 리턴한다.

Solution

class Solution {
    public int maxCount(int m, int n, int[][] ops) {        
    	int minX = m;
        int minY = n;
        for (int i=0; i < ops.length; i++) {
            minX = Math.min(minX, ops[i][0]);
            minY = Math.min(minY, ops[i][1]);
        }

        return minX * minY;
    }
}

Reference

https://leetcode.com/problems/range-addition-ii/