Daily LeetCode Challenge - 1351. Count Negative Numbers in a Sorted Matrix

Problem From.
https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/

오늘 문제는 각각의 행과 열이 모두 내림차순으로 정렬되어있는 matrix 가 주어질때, 음수의 갯수를 반환하는 문제였다.

이 문제는 O(N^2) 의 시간복잡도를 가진 방법으로도 풀 수있지만 O(M+N) 시간 복잡도를 가진 해답으로 풀기 위해, binary search 를 사용하였다.
각각의 행마다 이진탐색을 적용하여, 음수가 나오는 인덱스를 찾고, 한 행의 총 갯수에서 그 인덱스를 빼서 음수의 갯수를 구하였다.

class Solution {
    fun countNegatives(grid: Array<IntArray>): Int {
        var count = 0
        
        var mid = 0
        var start = 0
        var end = 0
        for(array in grid){
            start = 0
            end = array.size - 1                      
            while(start < end){
                mid = start +(end - start)/2
                if(array[mid] >= 0){
                    start = mid + 1
                }else{
                    end = mid
                }
            }
            if(array[start] < 0)
                 count += array.size - start
        }
        return count
    }
}