Find an Element from Sorted Matrix

Problem

Given an M * N matrix in which each row and each column is sorted in ascending order, write a method to find an element.

Solution

O(N + M) solution

By traversing matrix from upper right to lower left, we can solve this problem in O(N + M) time.

O((log N)²) solution

Searching a 2D Sorted Matrix Part II – LeetCode

As you can see, the run time complexity of this extreme case is O(lg n)2, which turns out to be even less than O(n).