Stack Bash - Master data structures and algorithms

Search a row and column sorted matrix

Given a 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.
Every row and every column is sorted in ascending order in the given matrix.
For example, if your function recieves the following 3x3 matrix and target number:
matrix = [
[1, 3, 8, 10],
[2, 5, 9, 11],
[3, 6, 10, 15],
[5, 7, 12, 18],
target = 6
Your function should return True.
Given the same matrix, if the target is 4, your function should return False.
Note how in matrix, every row and column is sorted, but is not necessarily greater than the previous row or column.

Try it

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


Time and Space Complexity

On each iteration we either remove an entire row or an entire column.
Therefore, our time complexity is O(m + 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.