LeetCode Solution: 240. Search a 2D Matrix II

#leetcode #dsa #programming #tutorial

Search a 2D Matrix II: The Clever Corner Approach You Need to Know!

Hey there, fellow coders! 👋 Vansh here, diving into another LeetCode adventure that looks tricky on the surface but has a surprisingly elegant solution. Today, we're tackling LeetCode 240: Search a 2D Matrix II.

This problem is a classic for a reason – it tests your ability to think outside the box and leverage unique properties of the input. If you've ever felt stuck with matrices, this one's a fantastic stepping stone! Let's unravel this mystery together.

The Problem: Finding Your Way in a Double-Sorted Grid

Imagine you have a large grid of numbers, like a spreadsheet. This isn't just any grid, though; it has two very special properties:

Rows are Sorted: If you look at any single row, the numbers go from smallest on the left to largest on the right.
Columns are Sorted: If you look at any single column, the numbers go from smallest at the top to largest at the bottom.

Your task? Given this special matrix and a target number, you need to efficiently determine if the target exists anywhere in the matrix.

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

Example 1:
Input: matrix = [[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]], target = 5
Output: true (You can see 5 is right there in the second row, second column!)

Example 2:
Input: matrix = [[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]], target = 20
Output: false (If you scan through, 20 isn't present in this matrix.)

The key here is "efficiently". A brute-force search (checking every single number) would work, but can we do better? Given the sorted nature, probably!

Intuition: Where to Start Looking?

When dealing with sorted data, binary search often comes to mind. You could run a binary search on each row, but that would be O(m * log n) (m rows, log n for each search). Can we do even better?

The real "aha!" moment comes when you realize that both sorting properties give us powerful information. Where in the matrix can we start such that if we compare our current number to the target, we can eliminate a significant portion of the search space?

Consider the four corners:

Top-Left (smallest): If matrix[0][0] is too big, we can't eliminate anything useful. If it's too small, we don't know if we should go right or down. Not ideal.
Bottom-Right (largest): Similar problem. If matrix[m-1][n-1] is too small, we don't know where to go.
Top-Right (mix of small and large): Ah, this is interesting!
- If matrix[0][n-1] is equal to target, we found it!
- If matrix[0][n-1] is greater than target, what does that tell us? Since this is the largest element in its row, and all elements below it in its column are even larger, we know target cannot be in the current column (or any element below the current position). So, we can safely move left to a smaller column!
- If matrix[0][n-1] is less than target, what now? Since this is the smallest element at the end of its column, and all elements to its left in the current row are even smaller, we know target cannot be in the current row (or any element to the left of the current position). So, we can safely move down to a larger row!
Bottom-Left (mix of small and large): This corner also works with similar logic! (Try it out as an exercise!)

The top-right (or bottom-left) corner provides a perfect pivot point. From here, each comparison allows us to eliminate either a full row or a full column! This is incredibly efficient.

Approach: The "Staircase" Search

Let's formalize the top-right corner approach:

Start at the Top-Right: Initialize two pointers, rowIndex = 0 (first row) and colIndex = n - 1 (last column).
Iterate and Compare: While rowIndex is within the matrix bounds (rowIndex < m) AND colIndex is within the matrix bounds (colIndex >= 0):
- Let currentElement = matrix[rowIndex][colIndex].
- Case 1: currentElement == target: We found our number! Return true.
- Case 2: currentElement < target: The currentElement is too small. Since all elements to the left in the current row are even smaller, and we need a larger value, the target cannot be in the current row (left of currentElement). We need to search in rows with potentially larger values. So, we move down to the next row: rowIndex++.
- Case 3: currentElement > target: The currentElement is too large. Since all elements below in the current column are even larger, and we need a smaller value, the target cannot be in the current column (below currentElement). We need to search in columns with potentially smaller values. So, we move left to the previous column: colIndex--.
Target Not Found: If our loop finishes (either rowIndex goes out of bounds or colIndex goes out of bounds), it means we've exhausted all possible search paths without finding the target. Return false.

This strategy looks like climbing down a staircase (or moving along a diagonal path), eliminating chunks of the matrix with each step.

Code: Bringing the Strategy to Life

Here's the Python implementation of our "staircase" search:

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        # Handle edge cases: empty matrix or empty rows
        if not matrix or not matrix[0]:
            return False

        rows = len(matrix)
        cols = len(matrix[0])

        # Start from the top-right corner
        # row pointer starts at the first row (index 0)
        # col pointer starts at the last column (index cols - 1)
        rowIndex = 0
        colIndex = cols - 1

        # Continue search as long as we are within matrix boundaries
        while rowIndex < rows and colIndex >= 0:
            element = matrix[rowIndex][colIndex] # Get the current element

            if element == target:
                # Target found!
                return True
            elif element < target:
                # Current element is too small.
                # Since rows are sorted left-to-right, all elements to the left
                # in the current row are even smaller.
                # Since columns are sorted top-to-bottom, we need to go down
                # to potentially find larger values.
                rowIndex += 1
            else: # element > target
                # Current element is too large.
                # Since columns are sorted top-to-bottom, all elements below
                # in the current column are even larger.
                # Since rows are sorted left-to-right, we need to go left
                # to potentially find smaller values.
                colIndex -= 1

        # If the loop finishes, the 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(m + n)
- In the worst-case scenario, our pointers rowIndex or colIndex will traverse at most m rows and n columns, respectively.
- At each step, we either increment rowIndex or decrement colIndex, effectively reducing the search space.
- We don't revisit cells or iterate over an entire row/column in each step. The total number of steps is proportional to m + n.
- This is significantly better than O(m * n) (brute force) or O(m * log n) (binary search on each row).
Space Complexity: O(1)
- We only use a few extra variables (rows, cols, rowIndex, colIndex, element) to store pointers and the current value.
- This constant amount of extra space means our solution is very memory-efficient.

Key Takeaways

This problem is a fantastic lesson in algorithmic thinking:

Leverage Properties: Always look for unique properties in your input data (like the double-sorted nature here). These properties are hints for more efficient algorithms.
Eliminate Search Space: The core idea of many efficient algorithms is to eliminate as much of the potential search space as possible with each decision.
Optimal Starting Points: The choice of where to start your search can drastically impact the algorithm's efficiency. Corners, especially top-right or bottom-left in this type of matrix, are often powerful pivot points.
Think Diagonally: Sometimes the best path through a 2D structure isn't horizontal or vertical, but diagonal!

Hope you enjoyed this dive into LeetCode 240! This problem is a great example of how a clever starting point and a simple set of rules can lead to a highly optimized solution. Keep practicing, and happy coding!

Authored by Vansh2710 | Published: 2026-04-01 00:20:33