Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/598.html

598. Range Addition II

Level

Easy

Description

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

Since each operation adds all the elements in the top left corner by one (according to the given row and the given column in each operation), simply obtain the minimum row r and the minimum column c among all the given operations, and the number of maximum integers in the matrix is r * c.

  • class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        if (m == 0 || n == 0)
            return 0;
        int maxRow = m, maxColumn = n;
        for (int[] op : ops) {
            maxRow = Math.min(maxRow, op[0]);
            maxColumn = Math.min(maxColumn, op[1]);
        }
        long maxArea = (long) maxRow * (long) maxColumn;
        int maxCount = (int) maxArea;
        return maxCount;
    }
}

public class Range_Addition_II {


    // ref: https://leetcode.com/articles/range-addition-ii/
	public class Solution {

	    int count = 1;

	    public int maxCount(int m, int n, int[][] ops) {
	        // my intuition, [0][0] is always the max integer
	        // and expand from [0][0] to probe for the same integer
	        // bsf: search [0][0]

	        if (m <= 0 || n <= 0) {
	            return 0;
	        }

	        // @note: corner case, all 0 with no ops, should return m*n
            //  maximum elements will be the ones which lie in the intersection region of the rectangles representing the operations
	        int i = m; // 行
	        int j = n; // 列
	        for (int[] each: ops) {
	            i = Math.min(i, each[0]);
	            j = Math.min(j, each[1]);
	        }

	        return i * j;
	    }
	}

}


############

class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        for (int[] op : ops) {
            m = Math.min(m, op[0]);
            n = Math.min(n, op[1]);
        }
        return m * n;
    }
}

  • class Solution {
public:
    int maxCount(int m, int n, vector<vector<int>>& ops) {
        for (auto op : ops) {
            m = min(m, op[0]);
            n = min(n, op[1]);
        }
        return m * n;
    }
};

  • class Solution:
    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
        for a, b in ops:
            m = min(m, a)
            n = min(n, b)
        return m * n

############

class Solution(object):
  def maxCount(self, m, n, ops):
    """
    :type m: int
    :type n: int
    :type ops: List[List[int]]
    :rtype: int
    """
    return reduce(operator.mul, map(min, zip(*ops + [[m, n]])))


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

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

All Problems

All Solutions