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

Constraints:

  • 1 <= m, n <= 4 * 104
  • 0 <= ops.length <= 104
  • ops[i].length == 2
  • 1 <= ai <= m
  • 1 <= bi <= n
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: m, n, i, j, max_val, count
    integer, allocatable :: M(:, :)
    integer, allocatable :: ops(:, :)

    read(*,*) m, n
    allocate(M(m,n))
    do i = 1, m
        do j = 1, n
            M(i,j) = 0
        end do
    end do
    read(*,*) ops
    do i = 1, size(ops, 1)
        M(ops(i,1), ops(i,2)) = M(ops(i,1), ops(i,2)) + 1
    end do
    max_val = -huge(max_val)
    count = 0
    do i = 1, m
        do j = 1, n
            if (M(i,j) > max_val) then
                max_val = M(i,j)
                count = count + 1
            end if
        end do
    end do
    print '(I0)', count

end program main
❌ Compiled
❌ Executed
❌ Correct 
module MaxIntegers
    implicit none
    private
    public :: maxIntegers

contains

    function maxIntegers(m, n, ops) result(max)
        integer, intent(in) :: m
        integer, intent(in) :: n
        integer, intent(in) :: ops(:, :)
        integer :: max
        integer :: M(m, n)
        integer :: i, j, ai, bi

        ! Initialize the matrix with all 0's
        M = 0

        ! Perform the operations
        do i = 1, size(ops, 1)
            ai = ops(i, 1)
            bi = ops(i, 2)
            do j = 1, bi
                M(1:ai, j) = M(1:ai, j) + 1
            end do
        end do

        ! Count the maximum integers
        max = 0
        do i = 1, m
            do j = 1, n
                if (M(i, j) == 0) then
                    exit
                end if
                max = max + 1
            end do
        end do
    end function maxIntegers
end module MaxIntegers

! Test the function with some examples
program test_maxIntegers
    use MaxIntegers
    implicit none
    integer :: m, n, ops(2, 2)
    integer :: max

    ! Example 1
    m = 3
    n = 3
    ops = reshape([2, 2, 3, 3], shape(ops))
    max = maxIntegers(m, n, ops)
    write (*, '(A, I0)') 'Example 1: ', max

    ! Example 2
    m = 3
    n = 3
    ops = reshape([2, 2, 3, 3, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 3], shape(ops))
    max = maxIntegers(m, n, ops)
    write (*, '(A, I0)') 'Example 2: ', max

    ! Example 3
    m = 3
    n = 3
    ops = reshape([], shape(ops))
    max = maxIntegers(m, n, ops)
    write (*, '(A, I0)') 'Example 3: ', max
end program test_maxIntegers
🌐 Data from online sources 
def maxCount(m: int, n: int, ops: List[List[int]]) -> int:
    for op in ops:
        m = min(m, op[0])
        n = min(n, op[1])
    return m * n

The algorithm consists of iterating through each operation in the ops array and updating the values of m and n to be the minimum of their current value and the corresponding values in the operation. This is because the maximum integers will always be in the top-left corner of the matrix (0 <= x < ai and 0 <= y < bi). Once all operations have been considered, we multiply the final values of m and n to get the count of maximum integers in the matrix.

🌐 Data from online sources 
#include <vector>
using namespace std;

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

The algorithm consists of iterating through each operation in the ops array and updating the values of m and n to be the minimum of their current value and the corresponding values in the operation. This is because the maximum integers will always be in the top-left corner of the matrix (0 <= x < ai and 0 <= y < bi). Once all operations have been considered, we multiply the final values of m and n to get the count of maximum integers in the matrix.