Search a 2D Matrix

MEDIUM✓ CHIP-TIMEDLC #74 — FULL STATEMENT ↗

The drill: Decide whether a target value exists in a matrix where each row is sorted and every row's first value exceeds the previous row's last — effectively one long sorted list folded into a grid.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A grid of integers arrives, built so every row reads left-to-right in ascending order and each row's first entry is larger than the previous row's last entry — the whole grid is really one long sorted list folded at fixed intervals.

A target value is handed over alongside the grid, and the job is to report whether that value sits anywhere inside it — true if some cell matches, false otherwise.

Because rows chain together in strict order, there's no need to treat this as a two-dimensional search problem at all; the structure collapses into something a single sorted-array technique can handle directly.

EX 01

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

→ true

HIT IN THE FIRST ROW

EX 02

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

→ false

MISS BETWEEN ROWS

EX 03

matrix = [[1]] · target = 1

→ true

SINGLE CELL, HIT

grid dimensions stay modest — up to a few hundred rows and columns
values across the whole grid are ordered as one continuous ascending sequence
the grid always has at least one row and one column
only a true/false membership answer is expected, not a position

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

The matrix's ordering rule means flattening it row by row produces one fully sorted array — what search works on a single sorted array?

HINT 2 THE STRUCTURE

You don't need to actually flatten anything: an index into a virtual 1-D array of length rows*cols maps back to (row, col) with plain division and modulo.

HINT 3 ONE STEP FROM THE ANSWER

Binary search over indices 0..rows*cols-1; convert mid to matrix[mid / cols][mid % cols] and compare exactly as you would in a flat array.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE FLATTENED GRIDPATTERN · FLATTENED BINARY SEARCHmatrix 3×4 · target = 16

STEP 1

Flatten the 3×4 grid into one virtual sorted array of 12 values. Binary-search indices 0 to 11 for target 16.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/search-a-2d-matrix.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows, cols = len(matrix), len(matrix[0])
        lo, hi = 0, rows * cols - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            val = matrix[mid // cols][mid % cols]
            if val == target:
                return True
            if val < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return False

TIME O(LOG(M·N))SPACE O(1)PYTHON · RACE PACE · 14 LN

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for row in matrix:
            for val in row:
                if val == target:
                    return True
        return False

TIME O(M·N)SPACE O(1)PYTHON · TRAINING PACE · 7 LN

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length, cols = matrix[0].length;
        int lo = 0, hi = rows * cols - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int val = matrix[mid / cols][mid % cols];
            if (val == target) {
                return true;
            } else if (val < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return false;
    }
}

TIME O(LOG(M·N))SPACE O(1)JAVA · RACE PACE · 18 LN

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            for (int val : row) {
                if (val == target) {
                    return true;
                }
            }
        }
        return false;
    }
}

TIME O(M·N)SPACE O(1)JAVA · TRAINING PACE · 12 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED