Teaching Kids Programming: Videos on Data Structures and Algorithms
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
Bruteforce Search in a Matrix
We can do bruteforce search rows by rows, cols by cols, which takes O(MN) time:
1 2 3 4 5 6 | class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: for row in matrix: if target in row: return True return False |
class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: for row in matrix: if target in row: return True return False
Search Space Reduction Algorithm
We can either start at top-right corner or left-bottom corner. Then compare the target with the value in the cell, and move accordingly.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: rows = len(matrix) if 0 == rows: return False cols = len(matrix[0]) if 0 == cols: return False r, c = 0, cols - 1 while r < rows and c >= 0: if target > matrix[r][c]: r += 1 elif target < matrix[r][c]: c -= 1 else: return True return False |
class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: rows = len(matrix) if 0 == rows: return False cols = len(matrix[0]) if 0 == cols: return False r, c = 0, cols - 1 while r < rows and c >= 0: if target > matrix[r][c]: r += 1 elif target < matrix[r][c]: c -= 1 else: return True return False
This works because the rows and colums are sorted. The complexity is O(M+N) as it takes at most M+N steps from one corner to reach the corner at diagonal or find a match (target).
- How to Search in 2D Sorted Matrix?
- https://helloacm.com/teaching-kids-programming-search-in-a-2d-sorted-matrix/
- GoLang: Search a 2D Matrix
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Depth First Search Algorithm to Compute the Longest Tree Sum Path From Root to Leaf
Next Post: Algorithms to Count the Equivalent Pairs in an Array