Teaching Kids Programming – Search in a 2D Sorted Matrix

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:

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.

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) —