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.

sorted-matrix Teaching Kids Programming - Search in a 2D Sorted Matrix algorithms python teaching kids programming youtube video

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

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
445 words
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

The Permanent URL is: Teaching Kids Programming – Search in a 2D Sorted Matrix

Leave a Reply