## 題解

### 鋸齒狀走法

依據題意，從左下角開始走訪 matrix 遇到負數往上走，遇到正數往右走，最後把(當前 row 長度 - x 的位置)加總即是答案

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        # [
        #     [4,3,2,-1],
        #     [3,2,1,-1],
        #     [1,1,-1,-2],
        #     [-1,-1,-2,-3]
        # ]
        # [
        #     [3,2],
        #     [1,0]
        # ]
        # Time complexity: O(n+m)
        # Space complexity: O(1)
        m,n = len(grid),len(grid[0])
        output = 0
        x,y = 0,m-1
        while x < n and y >= 0:
            if grid[y][x] < 0:
                output += (n - x)
                y -= 1
            else:
                x += 1
        return output
        

### Binary Search

走訪每個 row 做 Binary Search ，鎖定正數的右邊界 (low bound)

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m,n = len(grid), len(grid[0])
        
        def binary_search(nums: List[int]):
            left, right = 0, n - 1
            pos_bound = 0
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] < 0:
                    right = mid - 1
                else:
                    pos_bound = mid + 1
                    left = mid + 1
            return n - pos_bound

        output = 0
        for nums in grid:
            output += binary_search(nums)

        return output