Stack Bash - Master data structures and algorithms

Search a sorted matrix

Given a sorted matrix of numbers of size m x n, and a target number, write a function that determines if the target number exists in the matrix.
For example, if your function recieves the following 3x3 matrix and target number:
matrix = [
[1, 3, 8],
[9, 21, 24],
[25, 28, 32]
target = 7
Your function should return False.
Given the same matrix, if the target is 21, your function should return True.
Note that every row is sorted. Each row starts with a number that is greater than the last number from the previous row.

Try it

Before you look at the solution, try to code it yourself.


Time and Space Complexity

Since we cut the problem in half in each iteration, the time complexity is O(log n).
There is no additional space required. So the space complexity constant O(1).

5 Essential Sorting & Searching Coding Interview Problems

Master Sorting & Searching by trying the coding challenges below.
  1. 1.Merge intervalsMedium
  2. 2.Kth largest in arrayMedium
  3. 3.Intersection of ArraysMedium
  4. 4.Search sorted matrixHard
  5. 5.Search row & col sorted matrixHard

Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.