My friend told me about an interesting algorithms problem he had come across and had not yet solved a while ago. We then worked on it together for some time, and eventually arrived at what believe to be a solution. This post is my attempt to recall the problem and our solution^{1}^{2}.
Warmup Problem
The problem has to do with finding a certain element of a matrix. Before getting to it, I want to start with a simpler case of the problem just to get used to things. We first need to know what we are searching for.
Definition
A local minimum of an array of numbers is an element that is (strictly) smaller than its all of its neighbors^{3}.
So, unsurprisingly, we are gonna be searching for local minima. One important thing, though, is that we assume no array has a repeated element.
Problem
Given any array of unique numbers, how do you find a local minimum in time ?
The solution, as hinted by the time complexity, is to essentially do a binary search. Start by looking at the middle element. If it’s a local minimum, you’re done. If it’s bigger than the element to the right, then recursively search the right half of the array.
Below in an example of this algorithm^{4} run on a list of unique numbers. The convention I use is that a number is large if its part of the numbers currently being considered by the algorithm, and it is huge if its the sole number the algorithm is looking at in the moment.
I coded this up in C++ as below
inline bool isSmallerLeft(const vector<int>& arr, int index) {
return index <= 0  arr[index] < arr[index1];
}
inline bool isSmallerRight(const vector<int>& arr, int index) {
return index + 1 >= arr.size()  arr[index] < arr[index+1];
}
inline bool isLocalMin(const vector<int>& arr, int index) {
return isSmallerLeft(arr, index) && isSmallerRight(arr, index);
}
int findLocalMin(const vector<int>& arr) {
int lo = 0, hi = arr.size()  1;
while (hi >= lo) {
int mid = (lo + hi) >> 1;
if (isLocalMin(arr, mid)) {
return mid;
} else if (isSmallerLeft(arr, mid)) {
lo = mid+1;
} else {
hi = mid1;
}
}
return 1;
}
Theorem
The above algorithm is correct and
Real Problem
Now that we got that out of the way, let’s look at something a little bit harder. Now, instead of considering 1D arrays, we’ll look for a local minimum of a matrix. We still require every number in the matrix to be unique, and it is (probably) important to keep in mind that when we search for local minima, any entry in a matrix has at most 4 neighbors.
Problem
Given an matrix of unique numbers, how can you find a local minimum in time at worse ?
The first thing to notice is that moving from arrays to matrices cause our time complexity to go from to . I don’t know about you, but this seemed strange to me. I don’t know of a clear realtion between and in the context of matrices. Furthermore, you would expect the matrix problem to be slower, but it actually has better complexity in relation to what it could be^{5}. What I mean is that in the worst case we check every element, so we can look at ratios to get a sense of how much better than worstpossible we are doing. In the array case, we get , but in the matrix case we get which is even smaller.
At this point, I encourage you to stop reading and spend the next couple of hours thinking about this problem, trying to come up with a solution. I’ll wait
You’re back; let’s say more stuff ^{6}. As it turns out, this lack of obvious relation between time complexites is related to there being fundamentally different ideas going into how each problem is solved. The issue with trying to generalize the case of arrays is that with matrices there’s no nice ordering on the indices. You could “flatten” an matrix into a large array and run the previous algorithm on it, and this would get a solution in time which is even better than we want, but you are not actually guaranteed to get a local minimum by doing this! ^{7} If this isn’t obvious, stop for a second and convince yourself that it is. Below, you probably want to read the footnotes.
Instead, here’s the solution my friend and I came up with. Start with the middle row, and find its absolute (read: not local) minimum ^{8}. If its a local minimum, we win. If not, then either the value above or below it is smaller. Recursively find a local minimum in the halfmatrix containing the smaller value ^{9}. That’s it. Note that because of the nature of the algorithm, the only things we consider as possible local minima are the absolute minimal elements of rows.
Before looking at an example, let’s calculate its time complexity on an matrix. It is
where we consecutively look at matrices of size
The above calucation was informal, but that’s ok since its correct. Below is an example run of the algorithm with the same conventions as before with an addition of a star by the row or column whose minimum was found.
Exercise
Write code that performs this algorithm, and count the number of steps (comparisons) it takes to find a local minimum on a large sample of random matrices. See if this number is actually roughly as expected.
Finally, a far too wordy proof…
Theorem
This algorithm is correct with time complexity .
Take some time to make sure this proof makes sense to you and is legit. If after a while, you’re still not convinced and you know a case where things go wrong, then leave a comment telling me where I went wrong.
Bonus
This post lacked much motivation and insight into where these solutions came from, and I usually like to try to have those things. I won’t include them here, but I will say I feel I somewhat robbed you of the chance to solve these problems yourself, so here’s an (unrelated) bonus problem I found just before writing this post. It’s not quite as difficult as this problem, but (hopefully) not immediately obvious
Problem
Given a sorted element array where every element appears 2 times except for a single number appearing once, how do you find this number in time ?
As an example, given the array , you would return as your answer.

Warning: I’m not 100% sure our solution is correct. It’s fairly handwavy ↩

Warning: This post might end up being kinda dense because I’m not sure what to say other than “here’s a problem; here’s a solution” ↩

When we move on to matrices, most elements will have 4 neighbors. Diagonal elements are not neighbors. ↩

Modulo me being inconsistent about which element is the middle one ↩

I’m not an Algorithms person, and this is not a standard complexity comparing method. This is just a way I think/thought of things ↩

If you didn’t come up with a solution, you’re not alone. This problem originated in an Algorithms class here on a problem set, but was hard enough that the professor changed his mind after assigning it and decided to not make it mandatory. Instead, it became a bonus problem. ↩

There might be a way to fix this issue to end up with a working algorithm. I have not explored this option. ↩

If there are fewer columns than rows, start with the middle column ↩

Every step you end up rotating the matrix 90 degrees. For example, in the first step, you search a row of size n, but in the second you search a column of size n/2. Note that you don’t actually rotate the matrix because that would waste time. You just switch between rows and columns. ↩