LeetCode Solution: 74. Search a 2D Matrix

LeetCode 74: Search a 2D Matrix - Conquer the Grid with Binary Search!

Hey fellow coders and problem-solvers! 👋 Vansh2710 here, diving into another LeetCode adventure. Today, we're tackling a classic problem that brilliantly combines the elegance of a sorted structure with the power of binary search: "Search a 2D Matrix".

This problem is a fantastic stepping stone for understanding how seemingly complex 2D data structures can often be simplified and optimized using fundamental algorithms. Ready to unlock its secrets? Let's go!

---

Problem Explanation: What's the Challenge?

Imagine you're given a special kind of grid, an m x n matrix, filled with integers. This isn't just any grid, though; it has two super helpful properties:

1. Each row is sorted: If you pick any row and read it from left to right, the numbers are always increasing (non-decreasing, to be precise).
2. Rows are also "sorted" relative to each other: The very first number in any given row is always greater than the very last number of the row directly above it. Think of it like a staircase where each step starts higher than the previous one ended.

Your mission? Given this unique matrix and a target integer, you need to figure out if target exists anywhere in this matrix. The catch? You must do it super efficiently, in O(log(m * n)) time.

Let's look at an example to make it crystal clear:

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

Example 2:
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.)

Notice how the numbers 1,3,5,7 are sorted. Then 10 (first of second row) is greater than 7 (last of first row). 10,11,16,20 are sorted. 23 (first of third row) is greater than 20 (last of second row). This pattern is key!

---

Intuition: The "Aha!" Moment 💡

When you hear "sorted data" and "logarithmic time complexity" in the same sentence, what's the first algorithm that pops into your mind? If you thought Binary Search, you're absolutely on the right track!

Binary search works wonders on 1D sorted arrays. But we have a 2D matrix here. How can we apply binary search to it?

This is where the magic happens! Look at those two properties again:

• Each row is sorted.
• The first element of a row is greater than the last element of the previous row.

These two properties combined mean that if you were to "flatten" or "unroll" this entire 2D matrix into a single 1D array, that resulting 1D array would also be perfectly sorted!

Imagine taking all elements from the first row, then all elements from the second row, and so on, and concatenating them. You'd get something like [1,3,5,7,10,11,16,20,23,30,34,60]. See? It's completely sorted!

So, the "aha!" moment is: We can treat this 2D matrix as a single, giant, sorted 1D array and perform a standard binary search on it!

---

Approach: From 2D to 1D (and Back!)

Our strategy will be to simulate a binary search on this "flattened" 1D array. But how do we access elements if we're only actually given a 2D matrix? We need a way to map the index of an element in our conceptual 1D array back to its corresponding (row, column) in the original 2D matrix.

Let's say our matrix has m rows and n columns. The total number of elements is m * n.
If we have a 1D index k (where k ranges from 0 to (m*n - 1)), how do we find its (row, col) in the 2D matrix?

• Row Calculation: In a matrix with n columns, each row contains n elements. So, an element at 1D index k would be in row k / n (integer division).
• Column Calculation: Within that row, its column index would be k % n (remainder after division by n).

For example, in a 3x4 matrix (n=4 columns):

• 1D index 0 -> (0/4, 0%4) -> (0, 0)
• 1D index 3 -> (3/4, 3%4) -> (0, 3)
• 1D index 4 -> (4/4, 4%4) -> (1, 0) (This is the start of the second row!)
• 1D index 7 -> (7/4, 7%4) -> (1, 3)
• 1D index 8 -> (8/4, 8%4) -> (2, 0) (Start of the third row!)

This mapping is the core of our solution!

Here's the step-by-step approach:

1. Initialize Pointers:
   • start: Set to 0 (representing the first element of our conceptual 1D array).
   • end: Set to (m * n) - 1 (representing the last element).
2. Binary Search Loop: Continue as long as start <= end.
3. Calculate Midpoint:
   • mid = start + (end - start) / 2 (This prevents potential integer overflow compared to (start + end) / 2).
4. Map Midpoint to 2D Coordinates:
   • currentRow = mid / numberOfColumns
   • currentColumn = mid % numberOfColumns
5. Retrieve Element: Get element = matrix[currentRow][currentColumn].
6. Compare and Adjust Pointers:
   • If element == target: We found it! Return true.
   • If element < target: The target is larger, so we need to search in the right half of our conceptual array. Update start = mid + 1.
   • If element > target: The target is smaller, so we need to search in the left half. Update end = mid - 1.
7. Target Not Found: If the loop finishes without finding the target, it means the target isn't in the matrix. Return false.

---

Code 🖥️

Here's the C++ implementation following our binary search approach:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // Get the 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 the conceptual 1D array
        int start = 0;
        int end = (numRows * numCols) - 1; // Total elements - 1

        // Perform binary search
        while (start <= end) {
            // Calculate the middle index for the 1D conceptual array
            int mid = start + (end - start) / 2;

            // Map the 1D 'mid' index back to 2D (row, col) coordinates
            int elementRow = mid / numCols;
            int elementCol = mid % numCols;

            // Get the element at the calculated 2D coordinates
            int element = matrix[elementRow][elementCol];

            // Compare the element with the target
            if (element == target) {
                return true; // Target found!
            } else if (element < target) {
                // Element is too small, search in the right half
                start = mid + 1;
            } else {
                // Element is too large, search in the left half
                end = mid - 1;
            }
        }

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

---

Time & Space Complexity Analysis

• Time Complexity: O(log(m * n))
  • We are performing a binary search on a conceptual 1D array of m * n elements.
  • In each step of binary search, we cut the search space in half.
  • Therefore, the number of operations is proportional to the logarithm of the total number of elements.
• Space Complexity: O(1)
  • We are only using a few extra variables (start, end, mid, numRows, numCols, etc.) which take up constant extra space regardless of the input matrix size.

This solution perfectly meets the O(log(m * n)) requirement!

---

Key Takeaways

• Binary Search Power: Don't limit binary search to just 1D arrays! It can be applied to any data structure that can be conceptually "flattened" into a sorted sequence.
• 2D to 1D Mapping: Understanding how to convert a 1D index to 2D coordinates (index / numCols for row, index % numCols for column) is a powerful technique for grid problems.
• Leverage Properties: Always pay close attention to the problem constraints and properties. The two "sorted" properties were the keys that unlocked this efficient solution.
• Edge Cases: Remember to handle edge cases like empty matrices or empty rows, though the problem constraints (1 <= m, n) might sometimes make this less critical depending on the platform's test cases.

---

That's it for LeetCode 74! I hope this breakdown helped you understand how to approach and solve this problem efficiently. Binary search is truly a fundamental algorithm, and seeing its application in a 2D context is a great way to solidify your understanding.

Happy coding!

---

Author Account: Vansh2710
Published: 2026-04-30 22:40:57