What is the brute force approach and complexity for Search a 2D Matrix II?

Scan all m · n cells and compare each one with target with time complexity O(m · n) and space complexity O(1).

What is the optimal approach and complexity for Search a 2D Matrix II?

Start top-right; too big → move left, too small → move down with optimal time complexity O(m + n) and space complexity O(1).

How do you identify the pattern for Search a 2D Matrix II?

Look for key signals in the prompt: "rows sorted, columns sorted" indicates Each corner cell has a clear order relationship with its row and column.; "no promise that a row starts after the previous ends" indicates The grid is NOT one sorted line → flattening (LC 74) is wrong.; "is target present?" indicates We only need a yes/no, so we can throw away anything that provably can't match..

Search a 2D Matrix II

Medium·LeetCode #240 Pro OnlyMedium

LeetCode

Problem Statement

You are given a grid matrix with m rows and n columns, and a number target. The grid has two promises:

Every row is sorted from left to right (ascending).
Every column is sorted from top to bottom (ascending).

Unlike Search a 2D Matrix, a row does not have to start after the previous row ends. Return true if target is somewhere in the grid, otherwise false.

Input

A 2D integer array matrix (m rows, n columns) whose rows and columns are each sorted ascending, and an integer target.

Output

true if target is in the matrix, otherwise false.

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

5 is at row 1, column 1.

Example 2

Input: same matrix, target = 20

Output: false

20 is not in the grid. Note that row 0 ends with 15 but row 1 starts with 2 — the rows overlap, so this grid is not one sorted line.

Constraints

• 1 ≤ m, n ≤ 300 (m rows, n columns)
• −10^9 ≤ matrix[i][j], target ≤ 10^9
• Every row is sorted ascending, left to right.
• Every column is sorted ascending, top to bottom.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“rows sorted, columns sorted”

→ Each corner cell has a clear order relationship with its row and column.

“no promise that a row starts after the previous ends”

→ The grid is NOT one sorted line → flattening (LC 74) is wrong.

“is target present?”

→ We only need a yes/no, so we can throw away anything that provably can't match.

Approach Complexity Ladder

Brute Force — check every cellO(m · n)O(1)

Scan all m · n cells and compare each one with target

Better — binary search every rowO(m · log n)O(1)

Each row is sorted, so run a binary search on each row

Optimal — staircase walk from the top-right cornerO(m + n)O(1)

Start top-right; too big → move left, too small → move down

Brute Force Intuition

Loop over every row and every column. Return true the moment a cell equals target.

Recognition rule for this sub-pattern:

Search a sorted matrix as one flat array, or binary search on where to cut two sorted arrays.

Remember this · Binary Search

Trigger

Sorted data, "minimum X such that…", "maximum X such that…", rotated arrays, answers that are monotonic (if X works, X+1 also works).

Think

Is there a yes/no question whose answers look like NNNNYYYY? Then binary search for the first Y.

Key question

What is my check function, and is it monotonic?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Binary Search translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Order Book Price Level Matching

std::lower_bound lookup in sorted price ticks for limit orders.

Explore Track

C++ Internals

CPU Branch Prediction & Cache Efficiency

Branch mispredictions in binary search and branchless mid-point arithmetic.

Explore Track

Search a 2D Matrix Median of Two Sorted Arrays