Searching a 2D Sorted Matrix Part I

Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is,

Table[i][j] ≤ Table[i][j + 1],
Table[i][j] ≤ Table[i + 1][j]

Google this problem and you will see that a lot of sites have posted this problem before me. So why another blog post?

I have read through forums, blog posts, and go through each comment people made. Surprisingly, most people had answered this question incorrectly. Especially the run time complexity part. They just put down the recurrence formula and “guess” the complexity. It just don’t work like that. To save you from frustration, I decided to post all possible solutions and my in-depth analysis here.

The most efficient solution is surprisingly easy to code. Its run time analysis is also easy to prove. It is also surprisingly easy to make incorrect assumptions if you are not careful.

Note:
For the sake of run time complexity analysis, we will assume that the matrix is a square matrix of size n x n. Your algorithm should work on matrix of size m x n though.

Elements are sorted across each row and each column in this 2D matrix. This is also known as a Young Tableau.

Hint:
If you are choosing a place to start from, try the top right corner. Or the bottom left corner.

Binary Search Solution:
Most people will observe the keyword “sorted”, which no surprise that the idea of applying Binary Search to each row (or to each column) came up immediately. As each row takes O(lg n) time to search, and there are a total of n rows, we are able to do it in O(n lg n) time. Of course, your interviewer will tell you that this is not a good enough solution. In fact, this is the first trap that you should look out for! Do not confine yourself into thinking that binary search is the only way to solve this problem.

Incorrect Solution:
Here is another trap that most people will fall into if they are not careful enough. This is based on an incorrect assumption that if the target element falls between two numbers in the first row, then the target element must be within that two column. If not, then the target element does not exist.

Assume that you are searching for 9. You scan through the first row and see that 9 appears between 7 and 11. Therefore, apply Binary Search on these two columns (highlighted in yellow below). This is wrong, try to look for 10 in the matrix. 10 does not belong to any of those two columns.

Apply binary search across the highlighted columns. Searches 9 but failed to search for 10.

What if we do the same to the rows too? That is, since 10 is between 3 and 10, we apply binary search both to the two rows and two columns (as highlighted in yellow below). Finally, 10 could be found now. Although it seems to work in this example matrix, this is an incorrect solution. Coming up with a counter example is left as an exercise to the reader.

Apply binary search across the highlighted rows and columns. Searches both 9 and 10 now. Is this solution correct? Try to come up with a counter example.

Diagonal Binary Search (Still not there yet):
Still not giving up, you keep on brainstorming on how you can do a Binary Search in a more efficient manner.

How about we traverse the matrix diagonally starting from the top right corner? We will call this method the Diagonal Binary Search method. You may also start from the bottom left corner, it doesn’t matter.

Assume that our target is ’10’. We start from the top right corner, which contains the element 15. Since 10 is less than 15, we could eliminate the entire column from consideration as illustrated below (Areas that are eliminated are colored in gray). This follows from the rule that the column is in sorted order.

Eliminated areas are shown in gray. We start from the upper right corner, and traverse in a diagonal pattern.

We apply binary search from element 1 to 11 on the first row. Since 10 is not found, we proceed to the next diagonal step, which is 12. 10 is less than 12, therefore we do a binary search from 2 to 8 across the second row. Since 8 is less than 12, you could skip doing a binary search anyway. Now, the eliminated areas are shown below. You could see that we continue next with element 9 and do a binary search across the third column from 14 to 23. Eventually we will find 10 following that.

Eliminated areas are shown in gray. We have just completed the second step.

As we traverse diagonally, there’s one less item to search for either across the row or column. Therefore, the run time complexity can be written as:

T(n) = lg n + lg (n-1) + lg (n-2) + ... + lg (1) 
     = lg n(n-1)(n-2)...(1) 
     = lg n!

Compared to the previous method, this is a tiny bit of improvement over the last method. Proof of lg n! is less than n lg n is left as an exercise to the reader.

» Continue reading Part II: Searching a 2D Sorted Matrix.

VN:F [1.9.22_1171]
Rating: 4.6/5 (27 votes cast)
Searching a 2D Sorted Matrix Part I, 4.6 out of 5 based on 27 ratings

23 thoughts on “Searching a 2D Sorted Matrix Part I

  1. Adrian M

    Hi, I like your solution!
    I am wondering if it is possible to have another solution

    My impression is that the diagonal (top-left to bottom-right) elements are greater than the entire submatrix (which starts at (0,0) and ends at that diagonal element) they lie in.

    Say you’re looking for element x
    Look for 2 diagonals (top-left to bottom-right) such that x>=d1 and x<=d2. Well if x==d1 or x==d2 we're done.
    Otherwise we have to search between these 2 diagonals. Let me try to draw it:
    This is the matrix:
    – – – |
    – – – |
    – – 9 |
    | | |17

    If we are looking for 10, we know it is bw 9 and 17 (on the diagonals). So we search only in the rows and column I marked with pipe "|".
    The runtime would be sth along: 2*log(d2) + 2*log(d2-1) + … 2*log(d1)

    VA:F [1.9.22_1171]
    0
    1. Moussa

      @Adrian M, I think you are wrong on “Otherwise we have to search between these 2 diagonals”. A counter example: switch the positions of “17” and “18” in the matrix above, and try to search “17”.

      VA:F [1.9.22_1171]
      +2
  2. Pingback: You are given an MxN matrix of numbers, with the property that numbers increase as you go down each column, and as you go right on each row. How can you efficiently check whether a given number is in the matrix? - Quora

  3. Kapil Dalwani (@kapildalwani)

    What is the running time of this?

    I think it should be O(M+n) or O(N) ? Since at every step we are just removing a row or column. Worst case the element is at lowest left corner if we are starting from top right. Total traversal is m + n. How is it log n!?

    VA:F [1.9.22_1171]
    +4
  4. Moussa

    In your approach, the binary search on each row may not be necessary. The solution provided by @rajiv takes only O(n).

    VA:F [1.9.22_1171]
    0
  5. New Jobs

    I agree with Kapil. The running time of diagonal binary search is O(N). in each step, we either go down or go left, so we can move as many as N + N steps to find a solution or reach a border.

    VN:F [1.9.22_1171]
    0
  6. Inderpreet

    Hi,

    I have the following question, if you can an efficient algorithm to solve the problem, then do mail me:

    if there is a matrix A[][] of order m and another matrix B[][] of order n such that (m>n) you have to find the occurance of matrix B[][] in matrix A[][].
    A[5][5]=1,2,3,4,5
    5,4,1,9,7
    2,1,7,3,4
    6,4,8,2,7
    0,2,4,5,8
    B[3][3]=1,9,7
    7,3,4
    8,2,7
    this matrix B exist in A.

    VA:F [1.9.22_1171]
    0
  7. IsaacForYou

    I think the author mistook one thing. When calculating, it should be
    (logn + 1) + (log(n-1) +1) + (log(n-2) + 1) …, he/she missed the 1 for checking diagonal element.

    In traditional way, after each compare, we simply move 1 step, which yields (1+1)+(1+1) + …

    given an N*N grid, the author’s approach is N+logN!, while the traditional one is just 2N.

    VN:F [1.9.22_1171]
    +2
  8. Pingback: kkbox 面試 | taikerliang

  9. Pingback: [leetcode] Search a 2D Matrix | 二维矩阵找其中某个element的位置 | Lexi's Leetcode solutions

  10. Pingback: Searching a 2D Sorted Matrix - JavaScript - GeniusCarrier

  11. theOtherWC

    Correct me if I’m wrong:

    (1) Regarding the algorithm that does binary search along the diagonal line, we can do divide and conquer in 2 smaller (n/2)x(n/2) grids. So the recurrence will be roughly T(n) = 2T(n/2) + logn, where logn is used to do binary search. From master’s theroem we see T(n) = O(n).

    (2) Regarding the algorithm that eliminates either one column or one row by comparing target with the right uppermost element, this is also an O(n) algorithm.

    VA:F [1.9.22_1171]
    0
  12. Rohit

    Isn’t the time complexity O(n) and not O(log n!)?

    While the algorithm is efficient, it seems complex.

    Following is a simpler one, takes O(n)
    e is the element at index
    x is the element we’re searching for.

    1. Go to topmost right corner.
    2. If ex, go left

    Repeat until you go out of bounds.

    Source : geekforgeeks

    VA:F [1.9.22_1171]
    0
  13. William Li

    The complexity is log(n!), which by Stirling’s approximation is equivalent to:
    log(n^n * e^(-n))
    = log(n^n) + log(e^(-n))
    = nlogn – n
    = n(logn – 1)
    = nlogn

    What am I missing here?

    VA:F [1.9.22_1171]
    0
  14. Pingback: find iso-cost points on a 3d grid efficiently with minimum costing of points - DL-UAT

  15. Pingback: [NineChap 2.1] Binary Search | 海淘好deal

  16. Pingback: LeetCode 240: Search a 2D Matrix II | helloyuan

  17. Pingback: Report all occurrences of an element in row wise and column wise sorted matrix in linear time - Techie Delight

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*