matrix.count_negative_numbers_in_sorted_matrix

Given an matrix of numbers in which all rows and all columns are sorted in decreasing order, return the number of negative numbers in grid.

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

Attributes

grid

test_grids

Functions

benchmark(→ None)

Benchmark our functions next to each other

count_negatives_binary_search(→ int)

An O(m logn) solution that uses binary search in order to find the boundary between

count_negatives_brute_force(→ int)

This solution is O(n^2) because it iterates through every column and row.

count_negatives_brute_force_with_break(→ int)

Similar to the brute force solution above but uses break in order to reduce the

find_negative_index(→ int)

Find the smallest negative index

generate_large_matrix(→ list[list[int]])

validate_grid(→ None)

Validate that the rows and columns of the grid is sorted in decreasing order.

Module Contents

matrix.count_negative_numbers_in_sorted_matrix.benchmark() → None

Benchmark our functions next to each other

An O(m logn) solution that uses binary search in order to find the boundary between positive and negative numbers

>>> [count_negatives_binary_search(grid) for grid in test_grids]
[8, 0, 0, 3, 1498500]
matrix.count_negative_numbers_in_sorted_matrix.count_negatives_brute_force(grid: list[list[int]]) → int

This solution is O(n^2) because it iterates through every column and row.

>>> [count_negatives_brute_force(grid) for grid in test_grids]
[8, 0, 0, 3, 1498500]
matrix.count_negative_numbers_in_sorted_matrix.count_negatives_brute_force_with_break(grid: list[list[int]]) → int

Similar to the brute force solution above but uses break in order to reduce the number of iterations.

>>> [count_negatives_brute_force_with_break(grid) for grid in test_grids]
[8, 0, 0, 3, 1498500]
matrix.count_negative_numbers_in_sorted_matrix.find_negative_index(array: list[int]) → int

Find the smallest negative index

>>> find_negative_index([0,0,0,0])
4
>>> find_negative_index([4,3,2,-1])
3
>>> find_negative_index([1,0,-1,-10])
2
>>> find_negative_index([0,0,0,-1])
3
>>> find_negative_index([11,8,7,-3,-5,-9])
3
>>> find_negative_index([-1,-1,-2,-3])
0
>>> find_negative_index([5,1,0])
3
>>> find_negative_index([-5,-5,-5])
0
>>> find_negative_index([0])
1
>>> find_negative_index([])
0
matrix.count_negative_numbers_in_sorted_matrix.generate_large_matrix() → list[list[int]]
>>> generate_large_matrix() 
[[1000, ..., -999], [999, ..., -1001], ..., [2, ..., -1998]]
matrix.count_negative_numbers_in_sorted_matrix.validate_grid(grid: list[list[int]]) → None

Validate that the rows and columns of the grid is sorted in decreasing order. >>> for grid in test_grids: … validate_grid(grid)

matrix.count_negative_numbers_in_sorted_matrix.grid
matrix.count_negative_numbers_in_sorted_matrix.test_grids