Search a 2D Matrix

Problem Statement

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix.

The matrix has these properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

What to notice first

• The matrix is essentially a sorted 1D array arranged in 2D form.
• You can treat it as a single sorted array and use binary search.
• Convert 1D index to 2D: row = mid // n, col = mid % n.

Examples

matrix	target	Output	Explanation
[[1,3,5,7],[10,11,16,20],[23,30,34,60]]	3	true	3 is at index [0,1]
[[1,3,5,7],[10,11,16,20],[23,30,34,60]]	13	false	13 doesn’t exist in matrix
[[1]]	1	true	Single element, matches
[[1,3]]	3	true	1D row search

Constraints

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

Real-World Applications

Where this pattern appears

• Database range queries — binary search on structured data tables.
• Image processing — search for values in pixel matrices.
• Game boards — efficient search in grid-based games.
• Spreadsheet lookups — fast value search in sorted tabular data.

Complexity Comparison

Approach	Time	Space	Notes
Binary Search 2D	O(log(m*n))	O(1)	Direct 2D indexing; most efficient
Flatten to 1D	O(log(m*n))	O(1)	Treats matrix as 1D array; elegant conversion

Approach 1: Binary Search (2D) (Recommended)

★ Recommended

Recognize that the matrix is essentially a sorted 1D array arranged in 2D form. Use binary search on the flattened index space, converting 1D index to 2D using:

• row = mid // n
• col = mid % n

This is the most intuitive approach since it directly mimics 1D binary search.

⏱ Time O(log(m*n)) Binary search on flattened size 💾 Space O(1) Only pointers

Step-by-step Example

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

Flattened: [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60] (conceptually)

Iteration	left	right	mid	Value	Decision
1	0	11	5	11	11 > 3; right = 4
2	0	4	2	5	5 > 3; right = 1
3	0	1	0	1	1 < 3; left = 1
4	1	1	1	3	Found!

2D Conversion: mid = 1 → row = 1 // 4 = 0, col = 1 % 4 = 1 → matrix[0][1] = 3 ✓

Pseudocode

function searchMatrix(matrix, target):
    m = len(matrix)
    n = len(matrix[0])
    left = 0
    right = m * n - 1

    while left <= right:
        mid = (left + right) / 2
        row = mid // n
        col = mid % n
        midValue = matrix[row][col]

        if midValue == target:
            return True
        elif midValue < target:
            left = mid + 1
        else:
            right = mid - 1

    return False

Solution Code

Python

search_2d_matrix_binary_search.py

from typing import List

def searchMatrix(matrix: List[List[int]], target: int) -> bool:
    """Binary search approach: O(log(m*n)) time, O(1) space"""
    if not matrix or not matrix[0]:
        return False

    m, n = len(matrix), len(matrix[0])
    left, right = 0, m * n - 1

    while left <= right:
        mid = (left + right) // 2
        mid_value = matrix[mid // n][mid % n]

        if mid_value == target:
            return True
        elif mid_value < target:
            left = mid + 1
        else:
            right = mid - 1

    return False

C++

search_2d_matrix_binary_search.cpp

#include <vector>
using namespace std;

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if (matrix.empty() || matrix[0].empty()) return false;

    int m = matrix.size(), n = matrix[0].size();
    int left = 0, right = m * n - 1;

    while (left <= right) {
        int mid = (left + right) / 2;
        int mid_value = matrix[mid / n][mid % n];

        if (mid_value == target) return true;
        else if (mid_value < target) left = mid + 1;
        else right = mid - 1;
    }

    return false;
}

Java

Search2DMatrixBinarySearch.java

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) return false;

        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, right = m * n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midValue = matrix[mid / n][mid % n];

            if (midValue == target) {
                return true;
            } else if (midValue < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return false;
    }
}

JavaScript

search_2d_matrix_binary_search.js

function searchMatrix(matrix, target) {
    if (!matrix || !matrix.length) return false;

    const m = matrix.length, n = matrix[0].length;
    let left = 0, right = m * n - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const mid_value = matrix[Math.floor(mid / n)][mid % n];

        if (mid_value === target) return true;
        else if (mid_value < target) left = mid + 1;
        else right = mid - 1;
    }

    return false;
}

Rust

search_2d_matrix_binary_search.rs

pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
    if matrix.is_empty() || matrix[0].is_empty() { return false; }

    let m = matrix.len();
    let n = matrix[0].len();
    let mut left = 0;
    let mut right = (m * n - 1) as i32;

    while left <= right {
        let mid = (left + right) / 2;
        let mid_idx = mid as usize;
        let mid_value = matrix[mid_idx / n][mid_idx % n];

        if mid_value == target { return true; }
        else if mid_value < target { left = mid + 1; }
        else { right = mid - 1; }
    }

    false
}

Go

search_2d_matrix_binary_search.go

package main

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 { return false }

    m, n := len(matrix), len(matrix[0])
    left, right := 0, m*n-1

    for left <= right {
        mid := (left + right) / 2
        midValue := matrix[mid/n][mid%n]

        if midValue == target {
            return true
        } else if midValue < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return false
}

Approach 2: Flatten (Conceptual 1D Binary Search)

✓ Simple

Treat the 2D matrix as a flattened 1D array. The key insight: element at 1D index i corresponds to 2D position (i // n, i % n). Apply standard binary search on this virtual 1D array.

This approach emphasizes the mathematical transformation rather than the algorithm itself.

⏱ Time O(log(m*n)) Same as approach 1 💾 Space O(1) No extra structures

Step-by-step Example

Input: matrix = [[1,3,5,7],[10,11,16,20]], target = 13

Virtual 1D Array Index Mapping:

Index:  0  1  2  3  4  5  6  7
Value:  1  3  5  7 10 11 16 20
Row:    0  0  0  0  1  1  1  1
Col:    0  1  2  3  0  1  2  3

Binary search on index space finds no match for 13.

Pseudocode

function searchMatrix(matrix, target):
    m = len(matrix)
    n = len(matrix[0])
    left = 0
    right = m * n - 1

    while left <= right:
        mid = left + (right - left) / 2
        row = mid // n
        col = mid % n
        value = matrix[row][col]

        if value == target:
            return True
        elif value < target:
            left = mid + 1
        else:
            right = mid - 1

    return False

Solution Code

Python

search_2d_matrix_flatten.py

from typing import List

def searchMatrix(matrix: List[List[int]], target: int) -> bool:
    """Flatten approach: O(log(m*n)) time, O(1) space"""
    if not matrix or not matrix[0]:
        return False

    row_count = len(matrix)
    col_count = len(matrix[0])

    left, right = 0, row_count - 1

    while left <= right:
        mid_row = (left + right) // 2
        if target < matrix[mid_row][0]:
            right = mid_row - 1
        elif target > matrix[mid_row][-1]:
            left = mid_row + 1
        else:
            return target in matrix[mid_row]

    return False

C++

search_2d_matrix_flatten.cpp

#include <vector>
#include <algorithm>
using namespace std;

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if (matrix.empty() || matrix[0].empty()) return false;

    int row_count = matrix.size();
    for (auto& row : matrix) {
        if (binary_search(row.begin(), row.end(), target)) return true;
    }
    return false;
}

Java

Search2DMatrixFlatten.java

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) return false;

        int m = matrix.length;
        int n = matrix[0].length;

        // Flatten to 1D: use the formula row = mid / n, col = mid % n
        int left = 0, right = m * n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int row = mid / n;
            int col = mid % n;
            int midValue = matrix[row][col];

            if (midValue == target) {
                return true;
            } else if (midValue < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return false;
    }
}

JavaScript

search_2d_matrix_flatten.js

function searchMatrix(matrix, target) {
    if (!matrix || !matrix.length) return false;

    for (let row of matrix) {
        if (row.includes(target)) return true;
    }
    return false;
}

Rust

search_2d_matrix_flatten.rs

pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
    for row in matrix {
        if row.binary_search(&target).is_ok() { return true; }
    }
    false
}

Go

search_2d_matrix_flatten.go

package main

import "sort"

func searchMatrix(matrix [][]int, target int) bool {
    for _, row := range matrix {
        if sort.SearchInts(row, target) < len(row) {
            return true
        }
    }
    return false
}

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

search_a_2d_matrix_space_optimized.py

"""
Solution for Search a 2D Matrix
"""

def solve():
    """Implementation for approach 3 of Search a 2D Matrix"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

search_a_2d_matrix_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Search a 2D Matrix
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

SearchA2dMatrixSpaceOptimized.java

/**
 * Solution for Search a 2D Matrix
 * Approach 3
 */
public class SearchA2dMatrixSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

search_a_2d_matrix_space_optimized.js

/**
 * Solution for Search a 2D Matrix
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

search_a_2d_matrix_space_optimized.rs

/// Solution for Search a 2D Matrix
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

search_a_2d_matrix_space_optimized.go

package main

import "fmt"

// Solution for Search a 2D Matrix
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Common Mistakes

Watch for these pitfalls

• Incorrect 2D-to-1D conversion: Use row = mid // n (integer division) and col = mid % n (modulo).
• Forgetting matrix dimensions: Always cache m and n to avoid repeated .length calls.
• Edge cases: Empty matrix, single element, target outside range.
• Integer overflow: In languages with fixed-size integers, be careful with left + (right - left) / 2.

Interview Tips

Key trade-offs to discuss

• Why not two binary searches? One on rows, then one on the target row? That’s also O(log m + log n), slightly worse than O(log(m*n)).
• What if the matrix isn’t sorted? You’d need O(m*n) scanning.
• Why the flattenconversion? It unifies 2D and 1D binary search, making the solution elegant.
• Can you do this without conversion? Yes—start from top-right or bottom-left and step based on comparisons.