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¹².

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³.

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 \(n\) unique numbers, how do you find a local minimum in time \(O(\log n)\)?

The solution, as hinted by the \(O(\log n)\) 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⁴ 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[index-1];
}

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 = mid-1;
  	}
  }
  return -1;
}

Theorem
The above algorithm is correct and \(O(\log n)\)

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 \(n\times n\) matrix of unique numbers, how can you find a local minimum in time at worse \(O(n)\)?

The first thing to notice is that moving from arrays to matrices cause our time complexity to go from \(O(\log n)\) to \(O(n)\). I don’t know about you, but this seemed strange to me. I don’t know of a clear realtion between \(\log n\) and \(n\) 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⁵. 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 worst-possible we are doing. In the array case, we get \(\frac{\log n}n\), but in the matrix case we get \(\frac n{n^2}=\frac1n\) 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\(\dots\)

You’re back; let’s say more stuff ⁶. 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 \(n\times n\) matrix into a large array and run the previous algorithm on it, and this would get a solution in time \(O(\log(n^2))=O(2\log n)=O(\log n)\) which is even better than we want, but you are not actually guaranteed to get a local minimum by doing this! ⁷ 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 ⁸. 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 half-matrix containing the smaller value ⁹. 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 \(T_n\) on an \(n\times n\) matrix. It is

where we consecutively look at matrices of size \(n\times n,(n/2)\times n,(n/2)\times(n/2),(n/4)\times(n/2),\dots\)

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 \(n\times n\) matrices. See if this number is actually roughly \(3n\) as expected.

Finally, a far too wordy proof…

Theorem
This algorithm is correct with time complexity \(O(n)\).

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 \(n\)-element array where every element appears 2 times except for a single number appearing once, how do you find this number in time \(O(\log n)\)?

As an example, given the array \(\{1,1,2,2,3,3,5,5,7,8,8,9,9\}\), you would return \(7\) as your answer.