What is the time and space complexity of Search a 2D Matrix II?

Time complexity: O(m + n). Space complexity: O(1).

Search a 2D Matrix II

Med

Concept

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Search a 2D Matrix II

Approach

Start from top-right. If current is greater than target, move left; if smaller, move down. Each move drops a whole row/column that cannot contain the target.

Complexity Analysis

Time: O(m + n)
Space: O(1)

Pattern

Binary Search (Classic)

Why It Works

In each step, sorted order guarantees one full row or one full column is eliminated, so the search region shrinks in linear combined steps.

Updated Feb 2026