Cracking The Coding Interview Together – Problem 10.9: Sorted Matrix Search

Picture this: you are building a high-performance inventory system where product IDs are indexed in a massive 2D grid. The database guarantees that every row is sorted from left to right, and every column is sorted from top to bottom. A client requests the coordinates of a specific product ID. If we scan every single cell linearly, we are looking at O(M × N) time—a complete non-starter for real-time systems operating at scale. How do we exploit the structural properties of this grid to trim our search space exponentially? Today, we are tackling Problem 10.9: Sorted Matrix Search. Let's dive in and architect a solution together.

Problem Statement

Given an M × N matrix in which each row and each column is sorted in ascending order, write a method to find the coordinates (row and column index) of a target element. If the element does not exist in the matrix, return false or an invalid coordinate pair.

Our operational goals are straightforward:

• Maximize search efficiency by avoiding brute-force scans.
• Handle edge cases gracefully, such as empty matrices, single-element matrices, and targets outside the matrix's boundaries.
• Keep space complexity to O(1) by avoiding unnecessary recursion or auxiliary data structures.

Analyze the Problem Together

When we first look at a matrix where rows and columns are sorted, our instinct might scream "Binary Search!" After all, binary search is the gold standard for sorted data. But let's look closer at the constraints. If we attempt a standard binary search on every row, our time complexity becomes O(M log N). If we do it on every column, we get O(N log M). Can we do better?

Let's find the "Aha!" conflict. Notice the corners of the matrix. If we start at the top-right corner, we have a fascinating property: everything to the left is smaller, and everything below is larger. Conversely, if we start at the bottom-left corner, everything above is smaller, and everything to the right is larger.

Let's compare our approaches:

By choosing the top-right pointer approach, we reduce our search problem from a 2D traversal into a constrained pathfinding problem that runs in linear time relative to the dimensions of the matrix.

Questions for the Interviewer

Before writing a single line of production code, a senior engineer always clarifies operational boundaries. Here are the questions we should ask:

• "Can we assume the matrix is guaranteed to be non-null and rectangular (i.e., every row has the exact same number of columns)?"
• "Are duplicate elements allowed within the matrix, and if so, does it matter which coordinate we return?"
• "What should our method return if the element is absent—a boolean, a custom coordinate object, or a sentinel value like [-1, -1]?"
• "Are we dealing with primitive integers, or could this be a generic type implementing Comparable?"

Think About the Solution

Let's map out our algorithm using the top-right corner strategy:

1. Initialize our row pointer row to 0 (the very top row).
2. Initialize our column pointer col to matrix[0].length - 1 (the rightmost column).
3. While row is within the matrix bounds and col is greater than or equal to 0:
   • Compare the current element matrix[row][col] with our target.
   • If it equals target, we found our match! Return the coordinates [row, col].
   • If the current element is greater than the target, we need a smaller number. Since values to the right are larger, we must move left by decrementing col (col--).
   • If the current element is less than the target, we need a larger number. Since values above are smaller, we must move down by incrementing row (row++).
4. If our pointers cross the matrix boundaries without finding the target, return null or [-1, -1].

Write Code and Explain

Here is our production-ready Java implementation. Notice how clean, concise, and robust it is against edge cases.

public class SortedMatrixSearch {

    // Class representing 2D coordinates
    public static class Coordinate {
        public int row;
        public int col;

        public Coordinate(int row, int col) {
            this.row = row;
            this.col = col;
        }

        @Override
        public String toString() {
            return "(" + row + ", " + col + ")";
        }
    }

    /**
     * Finds the coordinates of a target element in an M x N sorted matrix.
     *
     * @param matrix The 2D sorted integer array
     * @param target The value to search for
     * @return Coordinate object if found, or null if absent
     */
    public static Coordinate findElement(int[][] matrix, int target) {
        // Guard clause: validate matrix structure
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return null;
        }

        int row = 0;
        int col = matrix[0].length - 1; // Start at top-right corner

        while (row < matrix.length && col >= 0) {
            int current = matrix[row][col];

            if (current == target) {
                return new Coordinate(row, col);
            } else if (current > target) {
                col--; // Eliminate the current column
            } else {
                row++; // Eliminate the current row
            }
        }

        return null; // Target not found
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {15, 20, 40, 85},
            {20, 35, 80, 95},
            {30, 55, 95, 105},
            {40, 80, 100, 120}
        };

        Coordinate result = findElement(matrix, 55);
        System.out.println("Found 55 at: " + result); // Expected: (2, 1)
    }
}

Step-by-step walkthrough:

• We first check for null or empty matrices to prevent runtime exceptions.
• We set row = 0 and col = matrix[0].length - 1, placing our cursor at the top-right element.
• Inside the while loop, we evaluate the element. If our target is 55 and our current element is 85, 85 > 55 tells us that everything below 85 in this column is even larger. Thus, we decrement col to move left.
• This elimination step guarantees we never retrace our steps, driving our efficiency up.

Time & Space Complexity

Let's break down our resource consumption:

• Time Complexity: O(M + N), where M is the number of rows and N is the number of columns. In the worst-case scenario, our pointer travels from the top-right corner all the way to the bottom-left corner, traversing at most M rows and N columns.
• Space Complexity: O(1). We only store a few primitive integer variables for our pointers. No extra memory is allocated on the heap, making our footprint completely constant regardless of matrix size.

Why This Problem Matters (The Senior Perspective)

Matrix search algorithms are not just interview tropes; they mirror real-world problems in database query optimization, spatial indexing (like Quadtrees and R-trees), and computer graphics pixel mapping. Understanding how to navigate structured multi-dimensional data without resorting to brute force is a hallmark of engineering maturity. When designing systems that process large tabular data payloads in memory, choosing an O(M + N) traversal over an O(M × N) scan can mean the difference between a service timing out under load and responding in milliseconds.

Final Thoughts

Mastering matrix manipulation builds your spatial reasoning and sharpens your ability to identify hidden invariants in data structures. Take some time to modify this code—try implementing the bottom-left starting strategy or adapt it to find all occurrences of a target in a matrix with duplicate values. Keep practicing, stay curious, and I'll see you in the next post. Happy coding!