Search a 2D Matrix II | Leetcode 240

Welcome to our deep dive on Search a 2D Matrix II (Leetcode 240). Unlike a standard linear 1D sorted array, this Matrix maintains sorting algorithms spanning both the row and the column axes explicitly. Let's see how heavily we can harness that property.

Problem Statement

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example:

[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

Approach 1: Parallel Binary Search O(N * log M)

If every individual row is perfectly sorted natively, we don't have to brute-force loop through every single cell sequentially using an O(N * M) sweep!

We can iterate through each row (O(N)) one by one, and dynamically fire off a complete internal Binary Search (O(log M)) strictly targeting that individual horizon block.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
            
        def binary_search(row):
            left, right = 0, len(row) - 1
            while left <= right:
                mid = (left + right) // 2
                if row[mid] == target:
                    return True
                elif row[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return False
            
        for row in matrix:
            # We can skip the binary search entirely if the target mathematically 
            # bounds outside extreme margins of this entire horizontal sector
            if row[0] <= target <= row[-1]:
                if binary_search(row):
                    return True
                    
        return False

Complexity Analysis

Approach 2: Geometric Pointer Start (Top-Right Corner)

We can compress O(N * log M) all the way down natively into absolute O(N + M) by executing a massive insight utilizing the dual-sorting property of the grid.

If we anchor a pointer specifically at the Top-Right corner ([0, cols - 1]):

• Everything physically to the left of this slot geometrically is guaranteed to be SMALLER.
• Everything physically beneath this slot geometrically is guaranteed to be LARGER.

Therefore, we can treat the entire grid dynamically like a Binary Search Tree!

1. If the current square physically exceeds the target target < current, we step entirely LEFT, discarding the entire column dynamically!
2. If the current square is lacking dynamically target > current, we step DOWN, discarding the entire row dynamically!

graph TD
    A["Grid Corner Anchor [Row 0, Col M]"] --> B{"Current V vs Target"}
    B -- "Current > Target" --> C["Discard Column! Step LEFT (Col - 1)"]
    B -- "Current < Target" --> D["Discard Row! Step DOWN (Row + 1)"]
    
    C --> B
    D --> B

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]: return False
        
        rows = len(matrix)
        cols = len(matrix[0])
        
        # Start top right corner
        row, col = 0, cols - 1
        
        while row < rows and col >= 0:
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] > target:
                # Value is too big geometrically, move left to scan smaller variables
                col -= 1
            else:
                # Value is too small, shift downward iteratively
                row += 1
                
        return False

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (240)