LeetCode Solution: 74. Search a 2D Matrix

Conquer the Sorted Labyrinth: Searching a 2D Matrix with Binary Search Magic! ✨

Hey LeetCoders and aspiring developers! Vansh2710 here, ready to demystify another classic problem that's far simpler than it looks, especially if you know a neat trick. Today, we're diving into LeetCode problem 74: "Search a 2D Matrix."

This problem is a fantastic way to solidify your understanding of binary search and see how it can be applied in seemingly non-standard situations. If you've ever felt intimidated by anything beyond a simple sorted array, this post is for you!

The Quest: Search a 2D Matrix

Imagine you have a spreadsheet filled with numbers, but it has two very special properties:

1. Each row is perfectly sorted: From left to right, the numbers in every row are in increasing order.
2. Rows are also "sorted" relative to each other: The very first number in any row is always larger than the very last number of the row directly above it.

Here's an example:

matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
]

Notice how 7 (last in row 0) is less than 10 (first in row 1), and 20 (last in row 1) is less than 23 (first in row 2). This is a crucial detail!

Your mission? Given this matrix and an integer target, you need to figure out if target exists anywhere in the matrix. You also have a secret constraint: your solution must be super-efficient, running in O(log(m * n)) time. That's a big hint!

Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true (3 is right there in the first row!)

Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false (13 is nowhere to be found in this matrix.)

The "Aha!" Moment: Flattening the Matrix (Mentally!)

At first glance, you might think of iterating through each row and then doing a binary search on that row. That's a decent start, but it might not hit our O(log(m * n)) target directly. A binary search on m rows, each of length n, would be O(m * log n) in the worst case (if we had to search every row).

However, those two special properties of the matrix are screaming a secret: this 2D matrix behaves exactly like a single, giant, perfectly sorted 1D array!

Think about it:
If you take the first row [1, 3, 5, 7], then the second row [10, 11, 16, 20], and so on, and just concatenate them all together, you'd get:
[1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]

This new "flattened" array is completely sorted! And what do we use for finding elements efficiently in a sorted array? Binary Search!

The "aha!" is realizing we don't actually need to flatten the array. We can just pretend it's a 1D array and use clever math to translate our 1D binary search indices back into 2D (row, column) coordinates.

The Approach: Binary Search on a Virtual 1D Array

Here's how we apply the binary search magic:

1. Count Elements: First, determine the total number of elements in the matrix. If the matrix has m rows and n columns, the total number of elements is m * n. Let's call this totalElements.

2. Define Search Space:

   • Our "virtual" 1D array has indices from 0 to totalElements - 1.
   • Initialize start = 0 and end = totalElements - 1.

3. Binary Search Loop: Continue as long as start <= end.

   • Calculate mid: Find the middle index using mid = start + (end - start) / 2. This formula helps prevent integer overflow compared to (start + end) / 2.
   • Convert 1D mid to 2D (row, column): This is the clever part!
     • The row index for our mid element will be mid / n (integer division).
     • The column index for our mid element will be mid % n (modulo operator).
     • Why does this work? Imagine a 1D array mapped to a 2D grid. The first n elements are in row 0, the next n elements are in row 1, and so on. mid / n tells you how many full rows mid has "passed", giving you its row. mid % n tells you its position within that specific row.
   • Get the element: Retrieve the actual value from the matrix using matrix[mid / n][mid % n].
   • Compare and Adjust:
     • If element == target: Congratulations! You found it. Return true.
     • If element < target: The target must be in the "right half" of our virtual array (i.e., larger values). So, update start = mid + 1.
     • If element > target: The target must be in the "left half" of our virtual array (i.e., smaller values). So, update end = mid - 1.

4. Not Found: If the loop finishes (meaning start became greater than end), it means the target was not present in the matrix. Return false.

That's it! By treating the 2D matrix as a flat, sorted 1D array, we can leverage the power of binary search directly.

The Code

Here's the C++ implementation of this approach:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // Get dimensions of the matrix
        int numRows = matrix.size();
        if (numRows == 0) return false; // Handle empty matrix edge case

        int numCols = matrix[0].size();
        if (numCols == 0) return false; // Handle empty rows edge case

        // Initialize binary search pointers for our virtual 1D array
        int start = 0;
        // Total number of elements, our 1D array's last index
        int end = (numRows * numCols) - 1; 

        // Standard binary search loop
        while (start <= end) {
            // Calculate mid-point, preventing potential overflow
            int mid = start + (end - start) / 2;

            // Convert the 1D 'mid' index back to 2D (row, column) coordinates
            // row = mid / numCols
            // col = mid % numCols
            int element = matrix[mid / numCols][mid % numCols];

            // Compare the element at mid with the target
            if (element == target) {
                return true; // Target found!
            } else if (element < target) {
                // Target is larger, so search in the right half
                start = mid + 1;
            } else { // element > target
                // Target is smaller, so search in the left half
                end = mid - 1;
            }
        }

        // If the loop completes, the target was not found
        return false;
    }
};

Complexity Analysis

This is where our clever approach truly shines!

Aspect	Complexity	Explanation
Time Complexity	O(log(m * n))	We perform a binary search over m * n elements. Each step reduces the search space by half.
Space Complexity	O(1)	We only use a few constant extra variables (start, end, mid, numRows, numCols, element), regardless of the input matrix size.

This beautifully meets the O(log(m * n)) time complexity requirement!

Key Takeaways

• Look for Hidden Order: Many problems, especially involving matrices, might have implicit properties that transform them into simpler, well-known data structures (like a sorted array).
• Binary Search Power: Binary search isn't just for 1D arrays! With a little mathematical mapping, it can be applied to 2D structures or even more complex search spaces.
• 1D to 2D Index Mapping: Remember the trick: row = index / num_cols and col = index % num_cols is your go-to for converting a 1D index to 2D coordinates.
• Efficiency Matters: Understanding the time and space complexity helps you choose the most optimal algorithm, especially in competitive programming.

I hope this breakdown helped you understand how to approach this problem and empowered you to look for creative binary search applications! Keep coding, keep learning, and see you in the next post!

---

Author: Vansh2710 | Published: 2026-04-30 22:33:53