Given a m * 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

Example 3:
Input: grid = [[1,-1],[-1,-1]]
Output: 3

Example 4:
Input: grid = [[-1]]
Output: 1

 
Constraints:

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

Source: leetcode | Difficulty: EASY
Tags: Matrices

Sorting

Data structures

Starter code: class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        

Solutions:
class Solution:

	def countNegatives(self, grid: List[List[int]]) -> int:
		count = 0
		for arr in grid:
			for num in arr:
				if num < 0:
					count += 1
		return count


class Solution:

	def countNegatives(self, grid: List[List[int]]) -> int:
		counter = 0
		for i in grid:
			for j in i:
				if j < 0:
					counter += 1
		return counter


class Solution:

	def countNegatives(self, grid: List[List[int]]) -> int:
		length = len(grid[0])
		count = 0
		for inside in grid:
			a = 0
			b = len(inside) - 1
			while a <= b:
				middle = (a + b) // 2
				if inside[middle] < 0:
					if middle > 0 and inside[middle - 1] >= 0:
						count += length - middle
						break
					elif middle == 0 and inside[middle - 1] < 0:
						count += length
						break
					else:
						b -= 1
				else:
					a += 1
		return count


class Solution:

	def countNegatives(self, grid: List[List[int]]) -> int:
		count = 0
		for i in range(len(grid)):
			for j in range(len(grid[i])):
				print(grid[i][j])
				if grid[i][j] < 0:
					count += 1
		return count


class Solution:

	def countNegatives(self, grid: List[List[int]]) -> int:
		i = 0
		j = 0
		count = 0
		while i < len(grid):
			while j < len(grid[i]):
				print(grid[i][j])
				if grid[i][j] < 0:
					count += 1
				j += 1
			i += 1
			j = 0
		return count


class Solution:

	def countNegatives(self, grid: List[List[int]]) -> int:
		somme = 0
		for row in grid:
			for el in row:
				if el < 0:
					somme += 1
		return somme


class Solution:

	def countNegatives(self, grid: List[List[int]]) -> int:

		def binarysearch(arr):
			low = 0
			high = len(arr) - 1
			while low <= high:
				mid = (low + high) // 2
				if arr[mid] < 0:
					high = mid - 1
				else:
					low = mid + 1
			return low
		count = 0
		for arr in grid:
			val = binarysearch(arr)
			count += len(arr) - val
		return count


import numpy as np

class Solution:

	def countNegatives(self, grid: List[List[int]]) -> int:
		g = np.array(grid)
		g = list(np.concatenate(g))
		count = 0
		sum = 0
		for i in g:
			if sum + i < sum:
				count += 1
			sum = sum + i
		return count


class Solution:

	def countNegatives(self, grid: List[List[int]]) -> int:
		return str(grid).count('-')


class Solution:

	def countNegatives(self, grid: List[List[int]]) -> int:
		c = 0
		for r in grid:
			for i in range(len(r)):
				if r[i] < 0:
					c += len(r) - i
					break
		return c


class Solution:

	def countNegatives(self, grid: List[List[int]]) -> int:
		return len([c for r in grid for c in r if c < 0])


class Solution:

	def countNegatives(self, grid: List[List[int]]) -> int:
		y = 0
		for row in grid:
			l = 0
			r = len(row)
			while l < r:
				mid = l + (r - l) // 2
				if row[mid] < 0:
					r = mid
				else:
					l = mid + 1
			y += len(row) - r
		return y


class Solution:

	def countNegatives(self, grid: List[List[int]]) -> int:
		count = 0
		for arr in grid:
			count += len(arr) - self.NegStart(arr)
		return count

	def NegStart(self, arr):
		first = 0
		last = len(arr) - 1
		found = False
		while first <= last:
			midpoint = (first + last) // 2
			if arr[midpoint] < 0:
				last = midpoint - 1
			else:
				first = midpoint + 1
		return first