Count Negative Numbers in a Sorted Matrix

🏠 ⬅️ ➡️

Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.

Example 1:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] Output: 8 Explanation: There are 8 negatives number in the matrix.

Example 2:

Input: grid = [[3,2],[1,0]] Output: 0

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • -100 <= grid[i][j] <= 100

Follow up: Could you find an O(n + m) solution?

Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: m = 4, n = 4
    integer :: grid(m, n)
    integer :: i, j
    integer :: negative_count

    ! Example 1
    grid(:, :) = reshape([4, 3, 2, -1, 3, 2, 1, -1, 1, 1, -1, -2, -1, -1, -2, -3], shape(grid))
    write(*, '(A, I0)') 'Example 1: ', count_negatives(grid)

    ! Example 2
    grid(:, :) = reshape([3, 2, 1, 0, 1, 0], shape(grid))
    write(*, '(A, I0)') 'Example 2: ', count_negatives(grid)

contains

    function count_negatives(grid) result(negative_count)
        implicit none
        integer, intent(in) :: grid(:, :)
        integer :: i, j
        integer :: negative_count

        negative_count = 0
        do i = 1, size(grid, 1)
            do j = 1, size(grid, 2)
                if (grid(i, j) < 0) then
                    negative_count = negative_count + 1
                end if
            end do
        end do
    end function count_negatives

end program main
❌ Compiled
❌ Executed
❌ Correct 
module NegativeNumbersInSortedMatrix
    implicit none
    private
    public :: negativeNumbersInSortedMatrix

contains

    function negativeNumbersInSortedMatrix(grid) result(count)
        integer, intent(in) :: grid(:, :)
        integer :: count

        integer :: i, j

        count = 0
        do i = 1, size(grid, 1)
            do j = 1, size(grid, 2)
                if (grid(i, j) < 0) then
                    count = count + 1
                end if
            end do
        end do
    end function negativeNumbersInSortedMatrix
end module NegativeNumbersInSortedMatrix

program test_negativeNumbersInSortedMatrix
    use NegativeNumbersInSortedMatrix
    implicit none

    integer, parameter :: m = 4
    integer, parameter :: n = 4
    integer, parameter :: grid(m, n) = reshape([4, 3, 2, -1, 3, 2, 1, -1, 1, 1, -1, -2, -1, -1, -2, -3], [m, n])
    integer :: count

    count = negativeNumbersInSortedMatrix(grid)

    write (*, *) "Negative numbers in grid:", count

    contains

    subroutine check(expected, actual)
        integer, intent(in) :: expected, actual

        if (expected /= actual) then
            write (*, *) "Error: expected ", expected, " but got ", actual
            stop 1
        end if
    end subroutine check
end program test_negativeNumbersInSortedMatrix
🌐 Data from online sources 
def balanced_string(s):
    n = len(s)
    freq_map = {}
    for c in s:
        freq_map[c] = freq_map.get(c, 0) + 1

    i = 0
    result = n
    for j in range(n):
        freq_map[s[j]] -= 1
        while i < n and all(freq_map.get(c, 0) <= n // 4 for c in "QWER"):
            result = min(result, j - i + 1)
            freq_map[s[i]] += 1
            i += 1

    return result
  1. Create a frequency map of characters in the given string.
  2. Initialize two pointers, i and j, to traverse the string.
  3. Traverse the string with pointer j and decrease the frequency of the current character.
  4. Check if the frequency of all characters is less than or equal to n/4. If so, update the minimum length of substring.
  5. Increment pointer i while maintaining the frequency map until the frequency of any character becomes more than n/4.
  6. Return the minimum length of substring found.
🌐 Data from online sources 
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

int balancedString(string s) {
    int n = s.size();
    unordered_map<char, int> freq_map;
    for (char c : s)
        freq_map[c]++;

    int i = 0, result = n;
    for (int j = 0; j < n; j++) {
        freq_map[s[j]]--;
        while (i < n && freq_map['Q'] <= n / 4 && freq_map['W'] <= n / 4 && freq_map['E'] <= n / 4 && freq_map['R'] <= n / 4) {
            result = min(result, j - i + 1);
            freq_map[s[i]]++;
            i++;
        }
    }
    return result;
}
  1. Create a frequency map of characters in the given string.
  2. Initialize two pointers, i and j, to traverse the string.
  3. Traverse the string with pointer j and decrease the frequency of the current character.
  4. Check if the frequency of all characters is less than or equal to n/4. If so, update the minimum length of substring.
  5. Increment pointer i while maintaining the frequency map until the frequency of any character becomes more than n/4.
  6. Return the minimum length of substring found.