Log inSign up
mediumLeetCodeNot Started

Search a 2D Matrix

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

Arrays
Solve on LeetCode
Lesson

Problem Statement

You are given an m x n integer matrix matrix with the following two properties: - Each row is sorted in non-decreasing order. - The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Explanation: The element 3 is located at row 0, column 1.

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Explanation: 13 does not exist anywhere in the matrix.

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -104 <= matrix[i][j], target <= 104

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Standard 1D Binary Search algorithm (lower bound, mid computation)
  • 2D-to-1D and 1D-to-2D coordinate mapping arithmetic (row = idx / cols, col = idx % cols)

What You'll Learn

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

  • Master 2D-to-1D and 1D-to-2D coordinate transformation formulas (r = mid / n, c = mid % n).
  • Understand the distinction between continuous matrix monotonicity (LeetCode 74) and independent row/col sorting (LeetCode 240).
  • Implement clean, single-pass binary search over a virtualized multidimensional index space.

Pattern Recognition Trigger

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

Signals to Look For:

  • Matrix with sorted rows and first element of each row strictly greater than last element of previous row.
  • Requirement to search in logarithmic time O(log(M * N)).
  • Flattenable continuous sorted sequence in a 2D coordinate space.

Algorithmic Decision Tree:

  • If the entire matrix forms a continuous monotonic 1D sequence, apply Virtual 1D Binary Search with r = mid / N and c = mid % N.
  • If only individual rows and columns are independently sorted (LeetCode 240), use Top-Right Stepwise Search instead.

Connected Patterns:

Search a 2D Matrix IIFind Peak ElementSearch in Rotated Sorted Array

1. Linear Scan (Brute Force)

Intuition

Iterate across all m rows and n columns. If matrix[r][c] == target, return true. If traversal completes without matching, return false.

When to apply: Use to understand matrix dimensions and baseline membership check.

Linear Matrix Scan Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]
Current operationSTEP 1 OF 6
Matrix 3x4: row 0 is [1, 3, 5, 7]
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
c3
r0
1
↑ r=0,c=0
3
5
7
r1
10
11
16
20
r2
23
30
34
60
Variables at this step
r
0
c
0
val
1
Check / comparison
1 == 3 (false)
Decision / next transition
Advance to (0,1).
Why this step matters

Matrix 3x4: row 0 is [1, 3, 5, 7]. Target = 3. Check (0,0)=1.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public boolean searchMatrix(int[][] matrix, int target) {
4 if (matrix == null || matrix.length == 0) return false;
5 int m = matrix.length, n = matrix[0].length;
6 for (int r = 0; r < m; r++) {
7 for (int c = 0; c < n; c++) {
8 if (matrix[r][c] == target) return true;
9 }
10 }
11 return false;
12 }
13 }
14
15 public static void main(String[] args) {
16 Solution sol = new Solution();
17 int[][] matrix = {
18 {1, 3, 5, 7},
19 {10, 11, 16, 20},
20 {23, 30, 34, 60}
21 };
22 int target = 3;
23 System.out.println("Found target 3: " + sol.searchMatrix(matrix, target));
24 }
25}

Time & Space Complexity

  • Time complexity: O(m * n) — Worst-case scans all m*n elements.
  • Space complexity: O(1) — O(1) memory.

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. Double Binary Search (Row then Column)

Intuition

1. Binary search the first column to find row index r such that matrix[r][0] <= target <= matrix[r][n-1]. 2. If valid row exists, run a standard 1D binary search on row matrix[r] for target.

When to apply: Use to understand the two sorted dimensions of the matrix.

Double Binary Search Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]
Current operationSTEP 1 OF 6
Phase 1: Binary search rows on first col [1, 10, 23]
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
c3
r0
1
↑ Target in Row 0
3
5
7
r1
10
11
16
20
r2
23
30
34
60
Variables at this step
top
0
bot
0
targetRow
0
Check / comparison
target 3 < 10.
Decision / next transition
Target must be in upper half. bot = 0.
Why this step matters

Phase 1: Binary search rows on first col [1, 10, 23]. top=0, bot=2. midRow = 1 (val 10).

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public boolean searchMatrix(int[][] matrix, int target) {
4 if (matrix == null || matrix.length == 0) return false;
5 int m = matrix.length, n = matrix[0].length;
6
7 int top = 0, bot = m - 1;
8 while (top <= bot) {
9 int midRow = top + (bot - top) / 2;
10 if (target > matrix[midRow][n - 1]) {
11 top = midRow + 1;
12 } else if (target < matrix[midRow][0]) {
13 bot = midRow - 1;
14 } else {
15 int l = 0, r = n - 1;
16 while (l <= r) {
17 int midCol = l + (r - l) / 2;
18 if (matrix[midRow][midCol] == target) return true;
19 if (matrix[midRow][midCol] < target) l = midCol + 1;
20 else r = midCol - 1;
21 }
22 return false;
23 }
24 }
25 return false;
26 }
27 }
28
29 public static void main(String[] args) {
30 Solution sol = new Solution();
31 int[][] matrix = {
32 {1, 3, 5, 7},
33 {10, 11, 16, 20},
34 {23, 30, 34, 60}
35 };
36 int target = 3;
37 System.out.println("Found target 3: " + sol.searchMatrix(matrix, target));
38 }
39}

Time & Space Complexity

  • Time complexity: O(log m + log n) — O(log m) row search followed by O(log n) column search.
  • Space complexity: O(1) — Only scalar pointers are used.

3. Virtual 1D Binary Search (Optimal & Standard)

Intuition

Since the first integer of each row is greater than the last integer of the previous row, the entire matrix forms a single strictly sorted sequence of length m * n. 1. Initialize low = 0, high = m * n - 1. 2. Calculate mid = low + (high - low) / 2. 3. Map to 2D coordinates: row = mid / n, col = mid % n. 4. Compare matrix[row][col] with target. Standard binary search rules apply.

When to apply: Use as the cleanest and most mathematically compact optimal algorithm for this problem.

Virtual 1D Binary Search Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]
Current operationSTEP 1 OF 6
Virtual 1D array of size 12
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
c3
r0
1
↑ low=0
3
5
7
r1
10
11
↑ mid=5 (11)
16
20
r2
23
30
34
60
Variables at this step
low
0
mid
5
high
4
matrix[1][1]
11
Check / comparison
11 > 3 (target)
Decision / next transition
mid value is too large! Search left half: high = mid - 1 = 4.
Why this step matters

Virtual 1D array of size 12. low=0, high=11. mid = 5. Row = 5 / 4 = 1, Col = 5 % 4 = 1. Value = matrix[1][1] = 11.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public boolean searchMatrix(int[][] matrix, int target) {
4 if (matrix == null || matrix.length == 0) return false;
5 int m = matrix.length, n = matrix[0].length;
6 int low = 0, high = m * n - 1;
7
8 while (low <= high) {
9 int mid = low + (high - low) / 2;
10 int r = mid / n;
11 int c = mid % n;
12 if (matrix[r][c] == target) return true;
13 if (matrix[r][c] < target) low = mid + 1;
14 else high = mid - 1;
15 }
16 return false;
17 }
18 }
19
20 public static void main(String[] args) {
21 Solution sol = new Solution();
22 int[][] matrix = {
23 {1, 3, 5, 7},
24 {10, 11, 16, 20},
25 {23, 30, 34, 60}
26 };
27 int target = 3;
28 System.out.println("Found target 3: " + sol.searchMatrix(matrix, target));
29 }
30}

Time & Space Complexity

  • Time complexity: O(log(m * n)) — Binary search across a search space of m*n elements takes O(log(m * n)).
  • Space complexity: O(1) — O(1) auxiliary pointer variables.

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)Iterate through every cell sequentially until the target is found.Inspects all cells without exploiting sorted order.
2.Better — Two-Stage Binary SearchO(log M + log N)O(1)Binary search on row starting values to identify target row, then binary search within that row.Two distinct loops.
3.Optimal — Virtual 1D Binary SearchOptimalO(log(M * N))O(1)Treat the 2D grid as a virtual 1D array of length M * N using index mapping formulas r = mid / N and c = mid % N.None; optimal.

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: ` —
  • Edge Case — Input: `, Expected: ` —

Interview Tips & Best Practices

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

  1. Clarify whether each row is strictly greater than the preceding row (LeetCode 74 vs LeetCode 240).
  2. Explain the virtual 1D indexing equation: r = mid / n and c = mid % n before writing code.
  3. Highlight that O(log(M * N)) = O(log M + log N), which satisfies the logarithmic requirement.

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?

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

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

Back to DSA Sheet