Search a 2D Matrix

Mediumbinary-searchmatrixarray
Category: Binary Search
Companies that ask this question:
AmazonGoogleFacebookMicrosoft
LeetCode →NeetCode →

Approach

Search a 2D Matrix

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.

Examples

Example 1

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Intuition

The key insight is that the matrix is fully sorted - if we flatten it into a 1D array, it would be sorted. We can perform binary search on this "virtual" 1D array without actually creating it!

Mapping: Given index i in flattened array:

  • Row: i / cols
  • Col: i % cols

This lets us use standard binary search while working with the 2D structure.

Pattern Recognition

This is Binary Search on 2D Matrix with these characteristics:

  • Sorted 2D structure (fully sorted)
  • Search for specific value
  • Requires O(log mn) time
  • Can be reduced to 1D binary search problem

Approach

  1. Treat as 1D Array:

    • Total elements: m * n
    • Indices: 0 to m * n - 1

  2. Binary Search:

    • left = 0, right = m * n - 1
    • Calculate mid = left + (right - left) / 2
    • Convert mid to 2D: row = mid / n, col = mid % n
    • Access element: matrix[row][col]

  3. Standard Binary Search Logic:

    • If matrix[row][col] == target: Return true
    • If matrix[row][col] < target: Search right half
    • If matrix[row][col] > target: Search left half

  4. Not Found: Return false

Edge Cases

  • Empty matrix
  • Single row matrix (reduces to 1D binary search)
  • Single column matrix
  • Target smaller than all elements
  • Target larger than all elements
  • 1x1 matrix

Complexity Analysis

  • Time Complexity: O(log(m * n)) where m = rows, n = cols

    • Single binary search over m * n elements
    • Each step eliminates half the search space

  • Space Complexity: O(1)

    • Only using a few variables
    • No additional data structures

Alternative Approaches

  1. Two Binary Searches: O(log m + log n)

    • First binary search to find correct row
    • Second binary search within that row

  2. Linear Search Each Row: O(m * n)

    • Iterate through rows, check if target could be in row, search row
    • Too slow, doesn't meet requirements

Solution

java
1class Solution {
2    public boolean searchMatrix(int[][] matrix, int target) {
3        if (matrix == null || matrix.length == 0) {
4            return false;
5        }
6
7        int m = matrix.length;  // rows
8        int n = matrix[0].length;  // cols
9
10        // Binary search on "virtual" 1D array
11        int left = 0;
12        int right = m * n - 1;
13
14        while (left <= right) {
15            int mid = left + (right - left) / 2;
16
17            // Convert 1D index to 2D coordinates
18            int row = mid / n;
19            int col = mid % n;
20            int midValue = matrix[row][col];
21
22            if (midValue == target) {
23                return true;
24            } else if (midValue < target) {
25                left = mid + 1;
26            } else {
27                right = mid - 1;
28            }
29        }
30
31        return false;
32    }
33}
34
Loading visualizer...