Search a 2D Matrix

🎯

Search a 2D Matrix

mediumBINARY_SEARCHAmazonMicrosoftFacebook

Imagine you have a large spreadsheet sorted row-wise and column-wise, and you want to quickly find if a certain value exists without scanning every cell.

💡 This problem is about searching efficiently in a 2D matrix that is sorted in a special way. Beginners often struggle because they try to search row by row or column by column, missing the opportunity to use binary search by treating the matrix as a 1D sorted array.

📋

Problem Statement

Given an m x n matrix where each row is sorted in ascending order and the first integer of each row is greater than the last integer of the previous row, write a function that returns true if a given target value exists in the matrix, and false otherwise.

m == matrix.lengthn == matrix[i].length1 ≤ m, n ≤ 10^5 (total elements ≤ 10^5)-10^9 ≤ matrix[i][j], target ≤ 10^9

💡

Example

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

Outputtrue

3 is present in the first row, second column.

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

Outputfalse

13 is not present in the matrix.

• Empty matrix → false
• Matrix with one element equal to target → true
• Matrix with one element not equal to target → false
• Target smaller than smallest element → false
• Target larger than largest element → false

⚠️

Common Mistakes

Not handling empty matrix or empty rows

Code crashes or returns incorrect result

✅ Add checks for empty matrix or empty first row before searching

Incorrectly mapping 1D index to 2D indices

Accessing wrong elements leading to wrong answers

✅ Use row = index // n and col = index % n consistently

Using linear search instead of binary search on rows

Slower code that may time out on large inputs

✅ Implement binary search properly on each row

Not updating binary search boundaries correctly

Infinite loops or missed target

✅ Ensure left = mid + 1 or right = mid - 1 updates are correct

Assuming matrix is sorted in both rows and columns

Incorrect approach chosen, leading to wrong results

✅ Clarify problem constraints and choose approach accordingly

🧠

Brute Force (Nested Loops)

💡 This approach exists to establish a baseline and understand the problem fully by checking every element. It is simple but inefficient, which motivates better methods.

Intuition

Check every element in the matrix one by one until the target is found or all elements are checked.

Algorithm

1. Iterate over each row in the matrix.
2. Within each row, iterate over each element.
3. Compare the current element with the target.
4. If found, return true; if all elements checked and not found, return false.

💡 The nested loops make it easy to understand but hide the inefficiency of checking every element.

</>

Code

def searchMatrix(matrix, target):
    for row in matrix:
        for num in row:
            if num == target:
                return True
    return False

# Driver code
if __name__ == '__main__':
    matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
    target = 3
    print(searchMatrix(matrix, target))  # True

Line Notes

for row in matrix:Iterate over each row to access all elements

for num in row:Iterate over each element in the current row

if num == target:Check if current element matches the target

return FalseReturn false if target not found after full scan

public class Solution {
    public static boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            for (int num : row) {
                if (num == target) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        int target = 3;
        System.out.println(searchMatrix(matrix, target)); // true
    }
}

Line Notes

for (int[] row : matrix)Loop over each row in the matrix

for (int num : row)Loop over each element in the current row

if (num == target)Check if current element equals target

return falseReturn false if target not found after full scan

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

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    for (auto& row : matrix) {
        for (int num : row) {
            if (num == target) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    vector<vector<int>> matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
    int target = 3;
    cout << (searchMatrix(matrix, target) ? "true" : "false") << endl; // true
    return 0;
}

Line Notes

for (auto& row : matrix)Iterate over each row by reference for efficiency

for (int num : row)Iterate over each element in the current row

if (num == target)Check if current element matches target

return falseReturn false if target not found after full scan

function searchMatrix(matrix, target) {
    for (const row of matrix) {
        for (const num of row) {
            if (num === target) {
                return true;
            }
        }
    }
    return false;
}

// Test
const matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]];
const target = 3;
console.log(searchMatrix(matrix, target)); // true

Line Notes

for (const row of matrix)Loop over each row in the matrix

for (const num of row)Loop over each element in the current row

if (num === target)Check if current element equals target

return falseReturn false if target not found after full scan

⏱

Complexity

TimeO(m*n)

SpaceO(1)

We check every element once, so time is proportional to total elements. No extra space used.

💡 For a 100x100 matrix, this means 10,000 checks, which is slow for large inputs.

Interview Verdict: Accepted but inefficient

This approach works but is too slow for large matrices, so better methods are needed.

🧠

Binary Search on Each Row

💡 This approach improves over brute force by using binary search on each row, leveraging the sorted nature of rows.

Intuition

Since each row is sorted, we can binary search each row individually to find the target faster than scanning all elements.

Algorithm

1. For each row in the matrix:
2. Perform binary search to find the target in that row.
3. If found, return true immediately.
4. If target not found in any row, return false.

💡 The key is applying binary search on each row independently, which is faster than linear search but still not optimal.

</>

Code

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return True
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

def searchMatrix(matrix, target):
    for row in matrix:
        if binary_search(row, target):
            return True
    return False

# Driver code
if __name__ == '__main__':
    matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
    target = 3
    print(searchMatrix(matrix, target))  # True

Line Notes

left, right = 0, len(arr) - 1Initialize binary search boundaries

mid = (left + right) // 2Find middle index to check

if arr[mid] == target:Check if middle element is target

if binary_search(row, target):Return true immediately if target found in any row

public class Solution {
    public static boolean binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) return true;
            else if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            if (binarySearch(row, target)) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        int target = 3;
        System.out.println(searchMatrix(matrix, target)); // true
    }
}

Line Notes

int left = 0, right = arr.length - 1;Set initial binary search boundaries

int mid = left + (right - left) / 2;Calculate mid index safely to avoid overflow

if (arr[mid] == target) return true;Return true if target found at mid

if (binarySearch(row, target)) return true;Stop searching rows once target found

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

bool binarySearch(const vector<int>& arr, int target) {
    int left = 0, right = (int)arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return true;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

bool searchMatrix(const vector<vector<int>>& matrix, int target) {
    for (const auto& row : matrix) {
        if (binarySearch(row, target)) return true;
    }
    return false;
}

int main() {
    vector<vector<int>> matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
    int target = 3;
    cout << (searchMatrix(matrix, target) ? "true" : "false") << endl; // true
    return 0;
}

Line Notes

int left = 0, right = (int)arr.size() - 1;Initialize binary search boundaries

int mid = left + (right - left) / 2;Calculate mid index safely

if (arr[mid] == target) return true;Return true if target found

if (binarySearch(row, target)) return true;Return early if target found in any row

function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return true;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

function searchMatrix(matrix, target) {
    for (const row of matrix) {
        if (binarySearch(row, target)) return true;
    }
    return false;
}

// Test
const matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]];
const target = 3;
console.log(searchMatrix(matrix, target)); // true

Line Notes

let left = 0, right = arr.length - 1;Initialize binary search boundaries

const mid = Math.floor((left + right) / 2);Calculate middle index

if (arr[mid] === target) return true;Return true if target found

if (binarySearch(row, target)) return true;Return early if target found in any row

⏱

Complexity

TimeO(m * log n)

SpaceO(1)

We do binary search on each of the m rows, each binary search takes O(log n).

💡 For 100 rows and 100 columns, this means about 100 * 7 = 700 operations, much faster than brute force.

Interview Verdict: Accepted, better but not optimal

This approach is a good improvement but still not the best because it does not use the full matrix ordering.

🧠

Optimal Binary Search Treating 2D Matrix as 1D Sorted Array

💡 This approach fully exploits the matrix's sorted property by treating it as a single sorted array and applying binary search once, making it optimal.

Intuition

Since the matrix is sorted row-wise and the first element of each row is greater than the last of the previous, we can map 2D indices to 1D and binary search over the entire matrix as if it was a sorted list.

Algorithm

1. Calculate total elements as m * n.
2. Initialize left = 0 and right = total_elements - 1.
3. While left <= right:
4. Calculate mid = (left + right) // 2.
5. Map mid to 2D indices: row = mid // n, col = mid % n.
6. Compare matrix[row][col] with target.
7. If equal, return true.
8. If less, move left to mid + 1.
9. Else move right to mid - 1.
10. Return false if not found.

💡 Mapping 1D index to 2D coordinates is the key insight that allows binary search on the matrix.

</>

Code

def searchMatrix(matrix, target):
    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
        row, col = divmod(mid, n)
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

# Driver code
if __name__ == '__main__':
    matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
    target = 3
    print(searchMatrix(matrix, target))  # True

Line Notes

if not matrix or not matrix[0]:Handle empty matrix edge case

m, n = len(matrix), len(matrix[0])Get matrix dimensions

left, right = 0, m * n - 1Set binary search boundaries over entire matrix

row, col = divmod(mid, n)Map 1D mid index to 2D coordinates

public class Solution {
    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int m = matrix.length, n = matrix[0].length;
        int left = 0, right = m * n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int row = mid / n;
            int col = mid % n;
            if (matrix[row][col] == target) return true;
            else if (matrix[row][col] < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        int target = 3;
        System.out.println(searchMatrix(matrix, target)); // true
    }
}

Line Notes

if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;Check for empty matrix

int left = 0, right = m * n - 1;Initialize binary search boundaries

int row = mid / n;Calculate row index from mid

int col = mid % n;Calculate column index from mid

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

bool searchMatrix(const vector<vector<int>>& matrix, int target) {
    if (matrix.empty() || matrix[0].empty()) return false;
    int m = (int)matrix.size(), n = (int)matrix[0].size();
    int left = 0, right = m * n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int row = mid / n;
        int col = mid % n;
        if (matrix[row][col] == target) return true;
        else if (matrix[row][col] < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

int main() {
    vector<vector<int>> matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
    int target = 3;
    cout << (searchMatrix(matrix, target) ? "true" : "false") << endl; // true
    return 0;
}

Line Notes

if (matrix.empty() || matrix[0].empty()) return false;Handle empty matrix edge case

int left = 0, right = m * n - 1;Set binary search boundaries over entire matrix

int row = mid / n;Map mid index to row

int col = mid % n;Map mid index to column

function searchMatrix(matrix, target) {
    if (!matrix.length || !matrix[0].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 row = Math.floor(mid / n);
        const col = mid % n;
        if (matrix[row][col] === target) return true;
        else if (matrix[row][col] < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

// Test
const matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]];
const target = 3;
console.log(searchMatrix(matrix, target)); // true

Line Notes

if (!matrix.length || !matrix[0].length) return false;Check for empty matrix

let left = 0, right = m * n - 1;Initialize binary search boundaries

const row = Math.floor(mid / n);Calculate row index from mid

const col = mid % n;Calculate column index from mid

⏱

Complexity

TimeO(log(m*n))

SpaceO(1)

Binary search over all elements treats matrix as a sorted array, so time is logarithmic in total elements.

💡 For a 100x100 matrix, this means about 14 operations, which is very efficient.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews for this problem due to its efficiency and elegance.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always aim to code the optimal approach (Approach 3) after briefly mentioning the others.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(m*n)	O(1)	No	N/A	Mention only - never code
2. Binary Search on Each Row	O(m*log n)	O(1)	No	N/A	Mention as intermediate improvement
3. Optimal Binary Search Treating 2D as 1D	O(log(m*n))	O(1)	No	N/A	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem constraints and matrix properties.Step 2: Describe the brute force approach to show understanding.Step 3: Explain binary search on each row as an improvement.Step 4: Present the optimal binary search treating the matrix as 1D.Step 5: Code the optimal solution and test edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of binary search, ability to map 2D to 1D indices, and optimization skills.

Common Follow-ups

• What if the matrix is not sorted row-wise but each row and column is sorted? → Use a different search approach starting from top-right.
• How to find the position of the target if it exists? → Return the mapped 2D indices when found.

💡 These follow-ups test your adaptability to variations and your ability to extend the solution.

🔍

Pattern Recognition

When to Use

1) Matrix or 2D array is sorted row-wise with rows sorted ascending, 2) First element of each row > last element of previous row, 3) Need to search for a target efficiently, 4) Constraints allow binary search.

Signature Phrases

'Each row is sorted in ascending order''First integer of each row is greater than the last integer of the previous row'

NOT This Pattern When

Matrix search problems where rows and columns are sorted independently but not in a linear order (e.g., Search a 2D Matrix II).

Similar Problems

Search a 2D Matrix II - similar but matrix sorted both row-wise and column-wiseFind Peak Element - uses binary search on arraysSearch Insert Position - classic binary search variant

Practice

1. You need to ship packages within a given number of days. Each package has a weight, and you must ship packages in order without splitting any package. You want to find the minimum ship capacity to ship all packages within the deadline. Which algorithmic approach guarantees finding the optimal ship capacity efficiently?

easy

A. Greedy approach that assigns packages to days until capacity is reached, then moves to next day without binary search

B. Dynamic programming to find the minimum capacity by exploring all subsets of packages and days

C. Sorting packages and using a two-pointer technique to assign packages to days

D. Binary search on the answer space (capacity) combined with a feasibility check to verify if shipping within days is possible

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding a minimum capacity that allows shipping all packages in order within a fixed number of days.

2. Step 2: Recognize the pattern

   Binary searching the capacity (answer space) and checking feasibility is the optimal approach because capacity ranges between max package weight and sum of all weights, and feasibility can be checked in linear time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Binary search on answer space is classic for optimization with feasibility checks [OK]

Hint: Binary search on capacity range solves this optimally [OK]

Common Mistakes:

• Thinking greedy alone finds minimal capacity
• Confusing DP with subset sums
• Using two pointers without sorting relevance

2. Given the following code snippet, what is the final output when running with piles = [3, 6, 7, 11] and h = 8?

from math import ceil

def can_finish(piles, speed, h):
    hours = 0
    for pile in piles:
        hours += ceil(pile / speed)
        if hours > h:
            return false
    return true

def minEatingSpeed(piles, h):
    low, high = 1, max(piles)
    while low < high:
        mid = (low + high) // 2
        if can_finish(piles, mid, h):
            high = mid
        else:
            low = mid + 1
    return low

piles = [3,6,7,11]
h = 8
print(minEatingSpeed(piles, h))

easy

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Trace binary search iterations

   Initial low=1, high=11. mid=6: can_finish with speed=6 returns true (hours=3+1+2+2=8 ≤8), so high=6. Next mid=(1+6)//2=3: can_finish speed=3 returns false (hours=1+2+3+4=10 >8), so low=4. Next mid=(4+6)//2=5: can_finish speed=5 returns true (hours=1+2+2+3=8 ≤8), so high=5. Next mid=(4+5)//2=4: can_finish speed=4 returns true (hours=1+2+2+3=8 ≤8), so high=4. Now low=4, high=4, loop ends.

2. Step 2: Return final low value

   The minimum speed is 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Tracing confirms minimum speed is 4 [OK]

Hint: Check feasibility at mid speeds carefully [OK]

Common Mistakes:

• Off-by-one in binary search boundaries
• Miscounting hours with ceil division

3. Examine the following buggy code for finding the single non-duplicate element in a sorted array. Which line contains the subtle bug that can cause incorrect results or infinite loops?

medium

A. Line 11: updating high to mid - 1 may skip the single element

B. Line 5: parity check on mid is incorrect for odd indices

C. Line 7: comparison with nums[mid + 1] can cause index out of range

D. Line 3: mid calculation uses division without floor, resulting in float index

Solution

1. Step 1: Identify mid calculation issue

   Using '/' in Python 3 returns float, which cannot index arrays, causing errors or infinite loops.

2. Step 2: Confirm other lines are correct

   Parity checks and updates are correct; no out-of-range access due to loop conditions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   mid must be integer index; float causes failure [OK]

Hint: mid must be integer index, not float [OK]

Common Mistakes:

• Using '/' instead of '//' in Python 3
• Confusing parity logic
• Incorrect boundary updates

4. Suppose you want to find the first occurrence of a target value in a sorted array that may contain duplicates. Which modification to the classic binary search algorithm correctly achieves this?

hard

A. Return the first index where nums[mid] == target and check if previous element is different or mid == 0

B. Return any index where nums[mid] == target without further checks

C. Use linear search after binary search to find first occurrence

D. Modify binary search to always move low to mid + 1 when nums[mid] == target

Solution

1. Step 1: Understand problem with duplicates

   Classic binary search returns any matching index, not necessarily first occurrence.

2. Step 2: Modify binary search to check if mid is first occurrence

   When nums[mid] == target, check if mid == 0 or nums[mid-1] != target; if not, continue searching left half.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Ensures first occurrence by verifying previous element [OK]

Hint: Check previous element to find first occurrence [OK]

Common Mistakes:

• Returning any occurrence
• Linear search after binary search wastes time
• Moving low forward on match loses first occurrence

5. Suppose the problem is modified so that the two input arrays can contain duplicate elements and you want to find the median of the combined multiset where elements can be reused infinitely many times. Which modification to the binary search on value range approach correctly handles this scenario?

hard

A. Modify countLessEqual to count elements less or equal normally, but adjust total length to infinite, then return left directly.

B. Use the same binary search on value range but count elements less or equal considering infinite duplicates as infinite count.

C. Use binary search on value range with countLessEqual unchanged, but adjust the target count to half of the finite combined length ignoring duplicates.

D. Use binary search on value range with countLessEqual unchanged, but since duplicates are infinite, the median is the minimum element.

Solution

1. Step 1: Understand infinite duplicates impact

   Infinite duplicates mean total length is infinite, so median is the smallest value with countLessEqual ≥ half of infinite.

2. Step 2: Adjust countLessEqual and target

   Counting elements normally but total length infinite means target is infinite/2 = infinite, so median is left boundary where countLessEqual reaches infinite.

3. Step 3: Return left directly

   Since infinite duplicates, median is the smallest value that satisfies countLessEqual condition, so return left.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Infinite duplicates require adjusting total length and returning left [OK]

Hint: Infinite duplicates make total length infinite, median is smallest qualifying value [OK]

Common Mistakes:

• Counting duplicates as finite
• Ignoring infinite total length
• Returning min element incorrectly