Log inSign up
mediumLeetCodeNot Started

Search a 2D Matrix II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

- Integers in each row are sorted in ascending from left to right. - Integers in each column are sorted in ascending from top to bottom.

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
Explanation: 5 is located at matrix[1][1].

Example 2:

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 = 20
Output: false
Explanation: 20 does not exist anywhere in the matrix.

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • -109 <= matrix[i][j] <= 109
  • All the integers in each row are sorted in ascending order.
  • All the integers in each column are sorted in ascending order.
  • -109 <= target <= 109

Prerequisites

Before attempting this problem, you should be comfortable with:

  • 2D matrix coordinate navigation and boundary conditions
  • Row and column monotonicity properties in 2D grids

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Identify when a matrix acts like a Binary Search Tree by anchoring at an asymmetric corner.
  • Understand why corners (0, n-1) and (m-1, 0) provide unambiguous directional decisions unlike (0, 0).
  • Prune search spaces in O(M + N) without materializing auxiliary data structures.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Rows sorted left-to-right AND columns sorted top-to-bottom independently.
  • Search query where starting at (0, 0) or (m-1, n-1) is non-deterministic.
  • Target complexity is linear in terms of dimensions O(M + N).

Algorithmic Decision Tree:

  • Position the search pointer at the Top-Right (0, n-1) or Bottom-Left (m-1, 0) corner where the two orthogonal directions represent opposite monotonic directions (one increases, one decreases).
  • If matrix[r][c] > target: eliminate current column (c--).
  • If matrix[r][c] < target: eliminate current row (r++).

Connected Patterns:

Search a 2D Matrix (LeetCode 74)Kth Smallest Element in a Sorted MatrixCount Negative Numbers in a Sorted Matrix

1. Exhaustive Linear Scan

Intuition

Check all M x N elements without exploiting any sorted order.

Algorithm

  1. Step 1: Iterate row r from 0 to m - 1.
  2. Step 2: Iterate col c from 0 to n - 1.
  3. Step 3: If matrix[r][c] == target, return true.
  4. Step 4: If traversal completes without match, return false.

Exhaustive Linear Scan Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 4, 7, 11, 2, 5, 8, 12, 3, 6, 9, 16, 10, 13, 14, 17]
Current operationSTEP 1 OF 6
Start linear scan at top-left cell (0,0)
Visual state
Values and pointers at this exact step
pointers
S
1
4
7
11
0
↑ curr
1
2
3
Variables at this step
row
0
col
0
val
1
target
5
found
false
Check / comparison
matrix[0][0] = 1 != target (5)
Decision / next transition
Advance col pointer to 1.
Why this step matters

Start linear scan at top-left cell (0,0). Value is 1, target is 5. 1 != 5.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 bool searchMatrix(const std::vector<std::vector<int>>& matrix, int target) {
7 if (matrix.empty() || matrix[0].empty()) return false;
8 int m = matrix.size(), n = matrix[0].size();
9 for (int r = 0; r < m; ++r) {
10 for (int c = 0; c < n; ++c) {
11 if (matrix[r][c] == target) return true;
12 }
13 }
14 return false;
15 }
16};
17
18int main() {
19 Solution solver;
20 std::vector<std::vector<int>> matrix = {
21 {1, 4, 7, 11, 15},
22 {2, 5, 8, 12, 19},
23 {3, 6, 9, 16, 22},
24 {10, 13, 14, 17, 24},
25 {18, 21, 23, 26, 30}
26 };
27 std::cout << (solver.searchMatrix(matrix, 5) ? "true" : "false") << std::endl;
28 std::cout << (solver.searchMatrix(matrix, 20) ? "true" : "false") << std::endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(M * N) — Time complexity for Exhaustive Linear Scan.
  • Space complexity: O(1) — Space complexity for Exhaustive Linear Scan.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Row-by-Row Binary Search

Intuition

We can prune rows where target < matrix[r][0] or target > matrix[r][n-1]. For valid candidate rows, run binary search in O(log N).

Algorithm

  1. Step 1: Iterate over each row r from 0 to m - 1.
  2. Step 2: Check if target falls in row's bounds: matrix[r][0] <= target <= matrix[r][n - 1].
  3. Step 3: If in bounds, execute binary search on matrix[r] with left = 0, right = n - 1.
  4. Step 4: If target found in binary search, return true.
  5. Step 5: If all rows checked without match, return false.

Row-by-Row Binary Search Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 4, 7, 11, 2, 5, 8, 12]
Current operationSTEP 1 OF 6
Binary search on Row 0: [1, 4, 7, 11]
Visual state
Values and pointers at this exact step
pointers
S
1
4
7
11
0
↑ low=0
1
↑ mid=1
2
3
↑ high=3
Variables at this step
row
0
low
2
high
3
mid
1
midVal
4
target
5
Check / comparison
Row 0 mid: 4 < 5
Decision / next transition
Target must be in right half of row 0. Set low = mid + 1 = 2.
Why this step matters

Binary search on Row 0: [1, 4, 7, 11]. low=0, high=3. mid=1 (val=4). 4 < target (5).

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7 bool searchMatrix(const std::vector<std::vector<int>>& matrix, int target) {
8 if (matrix.empty() || matrix[0].empty()) return false;
9 int m = matrix.size(), n = matrix[0].size();
10 for (int r = 0; r < m; ++r) {
11 if (target >= matrix[r][0] && target <= matrix[r][n - 1]) {
12 if (std::binary_search(matrix[r].begin(), matrix[r].end(), target)) {
13 return true;
14 }
15 }
16 }
17 return false;
18 }
19};
20
21int main() {
22 Solution solver;
23 std::vector<std::vector<int>> matrix = {
24 {1, 4, 7, 11, 15},
25 {2, 5, 8, 12, 19},
26 {3, 6, 9, 16, 22},
27 {10, 13, 14, 17, 24},
28 {18, 21, 23, 26, 30}
29 };
30 std::cout << (solver.searchMatrix(matrix, 5) ? "true" : "false") << std::endl;
31 std::cout << (solver.searchMatrix(matrix, 20) ? "true" : "false") << std::endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(M * log N) — Time complexity for Row-by-Row Binary Search.
  • Space complexity: O(1) — Space complexity for Row-by-Row Binary Search.

3. Top-Right Stepwise Search (Z-Search)

Intuition

The top-right cell acts like the root of a Binary Search Tree: left moves decrease the value, down moves increase it. Each comparison rules out an entire row or column.

Algorithm

  1. Step 1: Initialize row pointer r = 0 and column pointer c = n - 1 (top-right corner).
  2. Step 2: Loop while r < m and c >= 0.
  3. Step 3: If matrix[r][c] == target, return true immediately.
  4. Step 4: If matrix[r][c] > target, target cannot be in column c. Decrement c (c--).
  5. Step 5: If matrix[r][c] < target, target cannot be in row r. Increment r (r++).
  6. Step 6: If loop exits without returning true, return false.

Top-Right Staircase Search Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 4, 7, 11, 2, 5, 8, 12, 3, 6, 9, 16]
Current operationSTEP 1 OF 6
Initialize pointer at top-right cell (row=0, col=3)
Visual state
Values and pointers at this exact step
pointers
S
1
4
7
11
0
1
2
3
↑ (r=0, c=3)
Variables at this step
row
0
col
3
val
11
target
5
action
eliminate_col
Check / comparison
matrix[0][3] = 11 > target (5)
Decision / next transition
All elements below 11 in col 3 are even larger (> 11). Eliminate col 3! col--.
Why this step matters

Initialize pointer at top-right cell (row=0, col=3). Value is 11, target is 5.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 bool searchMatrix(const std::vector<std::vector<int>>& matrix, int target) {
7 if (matrix.empty() || matrix[0].empty()) return false;
8 int m = matrix.size();
9 int n = matrix[0].size();
10
11 int r = 0;
12 int c = n - 1; // Top-right corner
13
14 while (r < m && c >= 0) {
15 if (matrix[r][c] == target) {
16 return true;
17 } else if (matrix[r][c] > target) {
18 c--; // Move left (smaller values)
19 } else {
20 r++; // Move down (larger values)
21 }
22 }
23
24 return false;
25 }
26};
27
28int main() {
29 Solution solver;
30 std::vector<std::vector<int>> matrix = {
31 {1, 4, 7, 11, 15},
32 {2, 5, 8, 12, 19},
33 {3, 6, 9, 16, 22},
34 {10, 13, 14, 17, 24},
35 {18, 21, 23, 26, 30}
36 };
37
38 std::cout << std::boolalpha;
39 std::cout << "Search 5: " << solver.searchMatrix(matrix, 5) << std::endl; // true
40 std::cout << "Search 20: " << solver.searchMatrix(matrix, 20) << std::endl; // false
41 std::cout << "Search 30: " << solver.searchMatrix(matrix, 30) << std::endl; // true
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(M + N) — Time complexity for Top-Right Stepwise Search (Z-Search).
  • Space complexity: O(1) — Space complexity for Top-Right Stepwise Search (Z-Search).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Linear ScanO(M * N)O(1)Check every cell in the matrix one by one.Inspects every cell.
2.Better — Row-by-Row Binary SearchO(M * log N)O(1)Perform binary search on each row independently.Iterates through all M rows.
3.Optimal — Top-Right Corner Stepwise SearchOptimalO(M + N)O(1)Start at (0, n-1). Prune an entire row or column in each step based on comparison with target.None; optimal linear bound.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Draw the 2D grid and highlight why (0, 0) fails but (0, n-1) or (m-1, 0) succeeds as a BST-like root.
  2. Differentiate this problem clearly from Search a 2D Matrix I (O(log(MN)) vs O(M+N)).
  3. Mention Divide and Conquer (quad-tree style) as an alternative O(M^{0.58} N^{0.58}) approach if the interviewer probes deeper.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Search a 2D Matrix II?

2.Why is the brute force approach suboptimal for large inputs in Search a 2D Matrix II?

3.Which data structure or technique enables the optimal solution for Search a 2D Matrix II?

Back to DSA Sheet