LeetCode Solution: 74. Search a 2D Matrix

#leetcode #dsa #programming #tutorial

Master Binary Search: From 1D Arrays to a Tricky 2D Matrix (LeetCode 74 Explained!)

Hey there, future coding superstars! 👋 Vansh here, ready to demystify another LeetCode challenge that might look intimidating at first glance, but is actually a brilliant application of a fundamental algorithm: Binary Search!

Today, we're diving into LeetCode Problem 74: Search a 2D Matrix. If you've ever felt like binary search was only for simple 1D arrays, prepare to have your mind blown. We'll uncover a cool trick that transforms this 2D problem into a familiar friend. Let's go! 🚀

🧐 Problem Explanation: What are we searching for?

Imagine you have a spreadsheet or a table of numbers. This isn't just any table; it has two very special properties:

Each row is sorted: If you look across any single row, the numbers are arranged from smallest to largest. Think of it like [1, 3, 5, 7] – perfectly ordered!
Rows are "sorted" relative to each other: The very first number in a new row is always larger than the very last number of the row before it. This means if row 1 ends with 7, row 2 must start with something like 10 or 11, never 8 or 2.

Here's an example:

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

Notice how 7 < 10 and 20 < 23. This property is super important!

Your mission: Given this special matrix and a target number, you need to quickly figure out if the target exists anywhere in the matrix.

The catch? You must solve it with O(log(m * n)) time complexity. If that sounds like tech-speak for "super fast," you're right! It's a huge hint towards a specific algorithm... 😉

Let's look at the examples:

Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true (Because 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 (No 13 to be found anywhere.)

🤔 The "Aha!" Moment: Flattening the Matrix

Okay, O(log(m * n)) time complexity on a sorted structure usually means one thing: Binary Search! But binary search works on 1D arrays, right? How do we apply it to a 2D matrix?

This is where those two special properties come into play.
Consider our example matrix again:

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

If you were to take all the numbers and just string them out in a single line, what would you get?

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

BAM! 🤯 It's a perfectly sorted 1D array!

This is the key insight. The problem cleverly disguises a simple binary search on a 1D array as a 2D matrix search. Our "aha!" moment is realizing we can treat this 2D matrix as if it were a single, long, sorted 1D array of m * n elements.

✍️ Approach: Binary Search in Disguise

So, if we're going to treat it like a 1D array, we need a way to convert our 1D binary search index back into 2D (row, column) coordinates.

Let m be the number of rows and n be the number of columns.
If we have a 1D index k (where 0 <= k < m * n), we can find its corresponding (row, col) like this:

row = k / n (integer division)
col = k % n (modulo operation)

Let's walk through the steps:

Initialize Search Space:
- Think of the matrix as a 1D array. The smallest "index" is 0.
- The largest "index" is (total_elements - 1). Since there are m * n elements, end = (m * n) - 1.
- So, start = 0 and end = (m * n) - 1.
Binary Search Loop:
- While start is less than or equal to end (meaning there's still a search space):
  - Calculate the mid index: mid = start + (end - start) / 2. (This prevents potential integer overflow compared to (start + end) / 2).
  - Convert mid to 2D coordinates:
    - currentRow = mid / n
    - currentCol = mid % n
  - Compare matrix[currentRow][currentCol] with target:
    - If matrix[currentRow][currentCol] == target: Great! We found it. Return true.
    - If matrix[currentRow][currentCol] < target: The number at mid is too small. This means the target (if it exists) must be in the "right half" of our conceptual 1D array. So, update start = mid + 1.
    - If matrix[currentRow][currentCol] > target: The number at mid is too large. This means the target (if it exists) must be in the "left half". So, update end = mid - 1.
  - Crucial for the next iteration: Re-calculate mid using the updated start and end values.
Target Not Found:
- If the loop finishes (meaning start > end), it means our search space has shrunk to nothing, and we never found the target. Return false.

That's it! By cleverly mapping 1D indices to 2D coordinates, we can leverage the power of binary search.

💻 Code Time!

Here's the C++ implementation of our strategy:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        if (m == 0) { // Handle empty matrix (no rows)
            return false;
        }
        int n = matrix[0].size();
        if (n == 0) { // Handle matrix with empty rows
            return false;
        }

        int start = 0;
        int end = (m * n) - 1; // Total elements - 1 for 0-indexed

        // Initial calculation of mid for the first iteration
        int mid = start + (end - start) / 2; 

        while (start <= end) {
            // Convert 1D 'mid' index to 2D (row, col) coordinates
            int row = mid / n; 
            int col = mid % n;

            if (matrix[row][col] == target) {
                return true; // Target found!
            } else if (matrix[row][col] < target) {
                // Current element is too small, search in the right half
                start = mid + 1;
            } else { // matrix[row][col] > target
                // Current element is too large, search in the left half
                end = mid - 1;
            }

            // Recalculate mid for the next iteration based on updated start/end
            mid = start + (end - start) / 2;
        }

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

⏱️ Time & Space Complexity Analysis

Let's break down how efficient our solution is:

Time Complexity: O(log(m * n))
- This is the hallmark of binary search! In each step, we effectively cut our search space in half.
- Since we're searching through m * n elements (conceptually), the number of operations required grows logarithmically with the total number of elements. This is incredibly fast, especially for large matrices!
Space Complexity: O(1)
- We are only using a few extra variables (start, end, mid, row, col) to keep track of our search. We're not creating any new data structures proportional to the input size. Hence, our space usage is constant.

🎯 Key Takeaways

Recognize Implicit Sorting: Sometimes, a problem doesn't explicitly say "this array is sorted," but gives you properties that imply it's sorted (like our two matrix properties). This is your cue to think about binary search!
Transform the Problem: Don't be afraid to mentally (or even physically, if needed) transform the input structure into something simpler or more familiar if it helps apply a known algorithm. Here, 2D to 1D was the trick!
1D to 2D Index Mapping: Remember the elegant index / num_columns for row and index % num_columns for column. This is a super handy pattern for grid-based problems.
Binary Search is Versatile: It's not just for sorted arrays! It can be adapted to various problems where you need to find an element or a condition within a monotonic (consistently increasing or decreasing) search space.

That's a wrap for LeetCode 74! I hope this breakdown helped you understand how to approach such problems and appreciate the power of binary search beyond its basic form. Keep practicing, and you'll be solving these challenges like a pro in no time! Happy coding! ✨

Authored by Vansh2710
Published: 2026-03-31 23:40:02