598. Range Addition II

leetcode easy

#array#csharp#easy#leetcode#math#matrix

Task

Вам дана матрица M размером m x n, инициализированная нулями, и массив операций ops, где ops[i] = [ai, bi] означает, что значение M[x][y] должно быть увеличено на единицу для всех 0 <= x < ai и 0 <= y < bi.

Подсчитайте и верните количество максимальных чисел в матрице после выполнения всех операций.

Пример:

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.

C# solution

matched/original

public class Solution {
    public int MaxCount(int m, int n, int[][] ops) {
        int minA = m;
        int minB = n;
        foreach (var op in ops) {
            minA = Math.Min(minA, op[0]);
            minB = Math.Min(minB, op[1]);
        }
        return minA * minB;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaxCount(int m, int n, int[][] ops) {
        int minA = m;
        int minB = n;
        foreach (var op in ops) {
            minA = min(minA, op[0]);
            minB = min(minB, op[1]);
        }
        return minA * minB;
    }
}

Java solution

matched/original

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

JavaScript solution

matched/original

var maxCount = function(m, n, ops) {
    let minA = m;
    let minB = n;
    for (let op of ops) {
        minA = Math.min(minA, op[0]);
        minB = Math.min(minB, op[1]);
    }
    return minA * minB;
};

Python solution

matched/original

class Solution:
    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
        min_a = m
        min_b = n
        for op in ops:
            min_a = min(min_a, op[0])
            min_b = min(min_b, op[1])
        return min_a * min_b

Go solution

matched/original

func maxCount(m int, n int, ops [][]int) int {
    minA := m
    minB := n
    for _, op := range ops {
        if op[0] < minA {
            minA = op[0]
        }
        if op[1] < minB {
            minB = op[1]
        }
    }
    return minA * minB
}

Explanation

Algorithm

Все операции выполняются на прямоугольной подматрице изначальной матрицы M, заполненной нулями, с верхним левым углом в точке (0,0) и нижним правым углом для операции [i,j] в точке (i,j).

Максимальный элемент будет тем, на который выполнены все операции. Максимальные элементы будут находиться в области пересечения прямоугольников, представляющих операции. Для определения этой области нужно найти нижний правый угол пересекающейся области (x,y), который равен (min(op[0]), min(op[1])).

Количество элементов, находящихся в области пересечения, определяется как произведение координат x и y.

😎