Binary Search a Globally Sorted Matrix

Interview Problem Interview Medium Matrix / Grid Binary Search

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.searchMatrix(matrix, target). Rows are ascending and each row starts above the previous row's final value. Return whether target exists in O(log(rows*cols)).

Starter code

class Solution:
    def searchMatrix(self, matrix, target):
        pass

Test cases

later-row

Expected: true

Wizard outline

Step 1: Initialize Solution.searchMatrix
Replace the empty starter with the first real state owned by Solution.searchMatrix. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Missing case
Complete the readable core algorithm for one representative Interview case. Map one flattened binary-search index back to matrix row and column coordinates.
Step 4: Harden the Later Row boundary
Repair the reviewed boundary and pass the complete submission contract. The row-boundary guarantee makes flattened row-major order sorted. Standard binary search preserves the target's possible interval, and coordinate translation reads exactly the flattened middle value.

Footguns and prerequisites

Use columns for both index // columns and index % columns.
arrays strings two pointers sliding window

Reviewed references

LeetCode 74 — Search a 2D Matrix

Practice prerequisites

Find the First True Boundary(opens in a new tab)
Find the First True Boundary isolates every index before left is known false, while every index at or after right is known true or the sentinel len(flags). That focused state discipline is required when implementing search two dimensional matrix as a complete Interview Problem.

Recommended approach and implementation

Treat the matrix as one sorted array and translate a middle offset with division and remainder.

Why it works: The row-boundary guarantee makes flattened row-major order sorted. Standard binary search preserves the target's possible interval, and coordinate translation reads exactly the flattened middle value.

class Solution:
    def searchMatrix(self, matrix, target):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        rows, columns = len(matrix), len(matrix[0])
        left, right = 0, rows * columns - 1
        while left <= right:
            middle = (left + right) // 2
            value = matrix[middle // columns][middle % columns]
            if value == target:
                return True
            if value < target:
                left = middle + 1
            else:
                right = middle - 1
        return False