Search a Row-and-Column 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). Each row increases left-to-right and each column increases top-to-bottom. Return whether target exists in O(rows+cols).

Starter code

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

Test cases

found

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: Pass the Missing case
Complete the readable core algorithm for one representative Interview case. Start at a monotone corner where each comparison eliminates one row or one column.
Step 3: Harden the Later Row Small Value boundary
Repair the reviewed boundary and pass the complete submission contract. At top-right of the remaining rectangle, a value above target eliminates its entire column, while a value below target eliminates its entire row. Thus each move preserves every possible target cell.

Footguns and prerequisites

Rows are not globally ordered across boundaries, so flattened binary search is invalid for this variant.
arrays strings two pointers sliding window

Reviewed references

LeetCode 240 — Search a 2D Matrix II

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 sorted matrix two as a complete Interview Problem.

Recommended approach and implementation

Start at the top-right corner; move left when too large and down when too small.

Why it works: At top-right of the remaining rectangle, a value above target eliminates its entire column, while a value below target eliminates its entire row. Thus each move preserves every possible target cell.

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.
        """
        row = 0
        column = len(matrix[0]) - 1
        while row < len(matrix) and column >= 0:
            value = matrix[row][column]
            if value == target:
                return True
            if value > target:
                column -= 1
            else:
                row += 1
        return False

Similar exercises

Binary Search a Globally Sorted Matrix(opens in a new tab)