FAANG Interview Question - Binary Search on Sorted 2D Array | Leetcode 74 - Search a 2D Matrix

leetcode, coding interview question, data structures, data structures and algorithms, binary search

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[antileft]

This solution is basically treating the matrix as an array and applying a normal binary search in it, so its complexity is log(n*m), wich is amazing. You could also achieve a log(n) + log(m) by applying a binary search in the first elements of each row to find the number inmediatelly lower that the numer you’re searching for, and then picking that row to apply another binary search to find the number.

[youknowwhatlol]

Thanks so much for such videos! They are really really

[handmadesoap]

I actually don't feel comfortable with this type of indexing because the length, the number of row/colums of the list can be changed and pretty much everything gets changed so what I do is to check if the index of the current element is -1, which is the last element of the list

[franchello]

Don't use (l+r)/2 . Use l +(r-l)/2 instead.

[tra]

Can you please make long videos instead of shorts related to this content

Thank you anyway !

[gamerpedia]

So before watching I tried to come up with a solution

Start by taking half of the matrix rows rounded up, and check the last index (last row, last column) of the lower half
From there use the lower or upper half
Do this recursively until you have one row
Now, apply a traditional binary search.

I also wanted to prove its time complexity lol so I did some math
Each time you run the binary search on a group, you'll get floor(n/2) or ceil(n/2) items remaining
This means the worst case for each run is ceil(n/2)
Now, the way this worst case is maximized is if each iteration gives use an odd number, because it maximizes the amount of rows remaining in the next iteration
That means the worst case is ceil(n/2) where n = 2m+1
So ceil((2m+1)/2) = ceil(m + ½) = m+1
m = (n-1)/2 so (n+1)/2 gets us our worst case scenerio for each successive run

Since it's applied recursively, we need f(x+1) = (f(x)+1)/2 where x is the number of runs
Changing the equation gives us
2f(x+1) - f(x) = 1

A difference operator is
∆f(x) = f(x+1)-f(x)
So f(x+1) = f(x) + ∆f(x)

Which gives us
f(x) + 2∆f(x) = 1

Using some shady methods with § as phi and D as the derivative operator we can use Umbral Calc to say
∆ = §D§^(-1)
Substituting gets us f(x) + 2§D§^(-1) × f(x) = 1

Doing g(x) = §^(-1) × f(x) means
§g(x) + 2§g'(x) = 1

Applying §^(-1) on both sides gives
g(x) + 2g'(x) = 1
We can do something cool like this
2 × dg/dx = 1-g
2 × dg × 1/(1-g) = 1 dx
Through integrating both sides we get
-2ln(1-g) = x + C

Meaning
1-g = e^(-x/2 + C)

Giving us
g(x) = 1-Ce^(-x/2)

If you expand e^(-x/2) into its Taylor Series and then apply § using the property that §x^n = x_n then you get that
f(x) = 1 - C×2^(-x)

For a given n, we want f(0) to be n
This is because 0 runs of a number just gives us the number

So 1-C×2^(-0) = n => 1-C = n => C = 1-n
Applying this gets
f(x) = (n-1)2^(-x) + 1
Now, we want to find when f(x) gets lower than two, because at that point we only have one row left
So
(n-1)2^(-x) + 1 < 2
(n-1)2^(-x) < 1
(n-1) < 2^x
log_2(n-1) < x

This means as soon as x is greater than log_2(n-1), we for sure have one row
Since x is an integer (number of runs/steps/iterations), we want an integer that is for sure bigger than log_2(n-1)

Well we know that
0 ≤ log_2(n-1) - floor(log_2(n-1)) < 1
Meaning log_2(n-1) < floor(log_2(n-1)) + 1

All of this means that number of runs will not exceed floor(log_2(n-1)) + 1

However, that's just rows
To apply columns, we run the algorithm again
This means that the number of runs will not exceed:
floor(log_2(m-1)) + 1 + floor(log_2(n-1)) + 1 < log_2(m-1) + log_2(n-1) + 2 < log_2(mn) + 2

This means our algorithm runs in O(log(mn)) time, as per the instructions of the shown interview question.

[mdahsanraza]

Even if I solve millions of leet code questions what’s the point if I am not able to get the foot into their interviews!

[aaronmurphy]

Could yoy not flatten the matrix and just to bin search normally