Efficient Search in Row-and-Column Sorted Matrices

Welcome back! In our last lesson, we adapted binary search to handle a partially ordered structure—a rotated sorted array. The key was to find a property (one sorted half) that allowed us to confidently eliminate a portion of the search space. We're going to continue this theme of searching in partially ordered data structures, but this time, in two dimensions.

Today's lesson focuses on a classic interview problem: searching for a value in a matrix where each row and each column is sorted. Your goal is to learn an efficient strategy that leverages this special structure to eliminate an entire row or column with every comparison, avoiding a slow, brute-force search. This technique is often called "Staircase Search" or "Saddleback Search."

The Problem: A Special Kind of Matrix

Imagine you are given an m x n matrix with the following properties:

• Integers in each row are sorted in ascending order from left to right.
• Integers in each column are sorted in ascending order from top to bottom.

Here's an example:

$$\left[\begin{array}{ccccc}1& 4& 7& 11& 15\\ 2& 5& 8& 12& 19\\ 3& 6& 9& 16& 22\\ 10& 13& 14& 17& 24\\ 18& 21& 23& 26& 30\end{array}\right]$$

Notice that while rows and columns are sorted, the matrix as a whole is not. For instance, matrix[0][4] (15) is greater than matrix[1][0] (2). This means we can't simply treat the matrix as a giant sorted 1D array and apply a standard binary search.

From Brute Force to a Better Idea

How would we find a target value, say 5, in this matrix?

1. Brute Force: The simplest way is to iterate through every single cell. For an m x n matrix, this is an $O(m\times n)$ approach. It's correct, but we can do better by using the sorted property.

2. A Better Approach: Since each row is a sorted array, we could perform a binary search on each one. This would involve m binary searches, each taking $O(\log n)$ time, for a total time complexity of $O(m\log n)$. This is a significant improvement, but it doesn't use the fact that the columns are also sorted.

The take U forward video provides a great overview of these initial thoughts and sets the stage for the optimal solution.

The Optimal Approach: Eliminate a Row or Column

The most efficient solution comes from a clever insight about where to start our search. If we start at the top-left corner, and our target is larger, we don't know whether to move right or down. Both directions contain larger numbers. The same ambiguity exists at the bottom-right corner if our target is smaller.

However, if we start at the top-right corner (or bottom-left), our choices become unambiguous. Let's start at matrix[0][n-1]. Let this element be current.

• If target == current, we've found our element.
• If target < current, the target cannot be in the current column, because all elements below current are even larger. We can safely eliminate the entire last column and move one step to the left (col--).
• If target > current, the target cannot be in the current row, because all elements to the left of current are smaller. We can safely eliminate the entire current row and move one step down (row++).

This logic guarantees that in every step, we discard either a full row or a full column from our search space. This process continues until we find the target or our pointers move out of the matrix bounds.

The following image illustrates the decision to move left when the current element is greater than the target.

The video from take U forward has an excellent segment that explains why the top-right and bottom-left corners are the ideal starting points for this elimination strategy.

The "Staircase Search" Algorithm in Action

This search pattern traces a path that looks like a staircase, which is why it's often called "Staircase Search".

To solidify this, the following animated video provides a very clear, step-by-step walkthrough of the entire process. Seeing the pointers i and j move and the logic applied at each step is extremely helpful for building confidence.

Implementation and Complexity

Now let's look at how to translate this logic into code. The article from GeeksforGeeks provides a concise explanation and a JavaScript implementation.

As mentioned, starting from the bottom-left corner works just as well. The logic is slightly different but follows the same principle of elimination:

• Start at matrix[m-1][0].
• If target > current, the target can't be in this column (values above are smaller), so move right (col++).
• If target < current, the target can't be in this row (values to the right are larger), so move up (row--).

This GitHub resource provides an explanation for the bottom-left approach and includes a TypeScript implementation, which is perfect for your preferred language.

Complexity Analysis

• Time Complexity: In each step, we either increment the row index or decrement the column index. The row index starts at 0 and goes up to m-1, and the column index starts at n-1 and goes down to 0. In the worst case, the path will traverse from one corner to the opposite, covering at most m rows and n columns. Therefore, the total number of steps is at most m + n, giving a time complexity of $O(m+n)$. This is a huge improvement over $O(m\times n)$.
• Space Complexity: We only need to store the row and column indices. This requires a constant amount of extra space, so the space complexity is $O(1)$.

Conclusion

In this lesson, we've extended our search skills to two dimensions. While the problem might seem like a candidate for a complex binary search variant, the most elegant solution comes from a different kind of elimination strategy.

Here are the key takeaways:

• A matrix with sorted rows and columns has a special structure that can be exploited for efficient searching.
• The key is to start at a corner where comparisons lead to unambiguous decisions. The top-right or bottom-left corners are ideal for this.
• By comparing the target with the element at the current position, you can eliminate an entire row or column at each step.
• This "Staircase Search" algorithm achieves a time complexity of $O(m+n)$ with $O(1)$ space, which is optimal.
• This lesson highlights a crucial theme in algorithms: the principle of elimination is the heart of efficient searching, even if the implementation doesn't look like a classic while (left <= right) binary search.

In our next and final lesson for this module, we will explore one more powerful and abstract application of binary search: "binary searching the answer," where we search for a solution within a range of possibilities rather than for an element in a data structure.