How to Solve: Search a 2D Matrix (FAANG-Level Guide)

How to Solve: Search a 2D Matrix (FAANG-Level Guide)

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—master it, and you prove you can reduce 2D search to 1D binary search, a skill that separates senior candidates from the rest."

? WHAT YOU NEED TO KNOW FIRST

Before tackling this problem, ensure you understand: 1. Binary Search – How to search in a sorted 1D array in O(log n) time. 2. Matrix Traversal – How to convert between 2D indices (row, col) and a 1D index. 3. Edge Cases in Search – Handling empty matrices, single-row/column matrices, and duplicates.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Repeat this mental checklist for every "Search a 2D Matrix" problem:

1. Clarify the Matrix Properties
2. Is the matrix sorted row-wise? Column-wise? Both?
3. Are there duplicates? If yes, how should they be handled?

4. Are there empty rows/columns? Edge cases (1x1, 1xN, Nx1)?

5. Choose the Right Technique

6. If fully sorted (row-wise + column-wise), use Flattened Binary Search.
7. If row-wise sorted + first/last elements sorted, use Row Elimination + Binary Search.
8. If sorted in rows and columns but not fully, use Staircase Search.

9. If unsorted, use BFS/DFS (but expect O(mn) time).

10. Convert 2D to 1D (if using Binary Search)

11. For a matrix of size m x n, the 1D index mid maps to:

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

12. Implement Binary Search (if applicable)

13. Initialize left = 0, right = m n - 1.

14. While left <= right:

    • mid = left + (right - left) // 2
    • Convert mid to (row, col).
    • Compare matrix[row][col] with target.
    • Adjust left or right accordingly.

15. Handle Edge Cases

16. Empty matrix → Return False.
17. Single-row or single-column matrix → Treat as 1D array.

18. Duplicates → Decide if first/last occurrence is needed.

19. Optimize for Time & Space

20. Time: O(log(mn)) for binary search, O(m + n) for staircase search.

21. Space: O(1) for most approaches, O(mn) for BFS/DFS.

22. Test with Examples

23. Test with:
    • Target present in first/last row.
    • Target not present.
    • Single-row/single-column matrix.
    • Duplicates (if allowed).

? WORKED EXAMPLES

Example 1 – Basic (LeetCode 74: Search a 2D Matrix)

Problem: Write an efficient algorithm to search for a value target in an m x n matrix where: - Integers in each row are sorted in ascending order. - The first integer of each row is greater than the last integer of the previous row.

Solution (Flattened Binary Search):

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 - left) // 2

        row, col = mid // n, mid % n

        if matrix[row][col] == target:

            return True

        elif matrix[row][col] < target:

            left = mid + 1

        else:

            right = mid - 1

    return False

Time Complexity: O(log(mn)) Space Complexity: O(1)

Why This Works: - The matrix is fully sorted (row-wise + first element of each row > last element of previous row). - We treat it as a 1D sorted array and apply binary search.

Example 2 – Medium (LeetCode 240: Search a 2D Matrix II)

Problem: Write an efficient algorithm to search for a value target in an m x n matrix where: - Integers in each row are sorted in ascending order. - Integers in each column are sorted in ascending order. - No guarantee that first element of row > last element of previous row.

Solution (Staircase Search):

def searchMatrix(matrix, target):

    if not matrix or not matrix[0]:

        return False


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

    row, col = 0, n - 1  # Start from top-right


    while row < m and col >= 0:

        if matrix[row][col] == target:

            return True

        elif matrix[row][col] < target:

            row += 1  # Move down (larger values)

        else:

            col -= 1  # Move left (smaller values)

    return False

Time Complexity: O(m + n) Space Complexity: O(1)

Why This Works: - The matrix is sorted row-wise and column-wise, but not fully sorted. - Starting from top-right, we can eliminate a row or column in each step.

Example 3 – Hard/Follow-up (Search in a Sorted Matrix with Duplicates)

Problem: Same as LeetCode 240, but the matrix may contain duplicates. Return True if target exists, False otherwise.

Solution (Modified Staircase Search):

def searchMatrix(matrix, target):

    if not matrix or not matrix[0]:

        return False


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

    row, col = 0, n - 1  # Start from top-right


    while row < m and col >= 0:

        if matrix[row][col] == target:

            return True

        elif matrix[row][col] < target:

            row += 1

        else:

            col -= 1

    return False

Time Complexity: O(m + n) Space Complexity: O(1)

Why This Works: - Duplicates do not break the staircase search because we still eliminate rows/columns correctly. - If matrix[row][col] < target, moving down is safe (all elements to the left are smaller). - If matrix[row][col] > target, moving left is safe (all elements below are larger).

Follow-up: Return All Occurrences If the interviewer asks for all positions of target:

def searchMatrixAllOccurrences(matrix, target):

    if not matrix or not matrix[0]:

        return []


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

    row, col = 0, n - 1

    result = []


    while row < m and col >= 0:

        if matrix[row][col] == target:

            result.append((row, col))

            # Move left to find duplicates in the same row

            temp_col = col - 1

            while temp_col >= 0 and matrix[row][temp_col] == target:

                result.append((row, temp_col))

                temp_col -= 1

            # Move down to find duplicates in the same column

            temp_row = row + 1

            while temp_row < m and matrix[temp_row][col] == target:

                result.append((temp_row, col))

                temp_row += 1

            row += 1

            col -= 1

        elif matrix[row][col] < target:

            row += 1

        else:

            col -= 1

    return result

Time Complexity: O(m + n + k), where k is the number of occurrences. Space Complexity: O(k) (for storing results).

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. When you see ‘Search a 2D Matrix,’ follow this playbook:

1. Clarify the matrix properties – Is it sorted row-wise? Column-wise? Both? Are there duplicates?
2. Choose the right technique –
3. If fully sorted, flatten it and use binary search (O(log(mn))).
4. If row-wise + column-wise sorted, use staircase search (O(m + n)) from top-right.
5. If unsorted, fall back to BFS/DFS (O(mn)).
6. Convert 2D to 1D correctly – For binary search, row = mid // n, col = mid % n.
7. Handle edge cases – Empty matrix, single-row/column, duplicates.
8. Test with examples – Target in first/last row, not present, duplicates.

This pattern shows up constantly in interviews. Nail it, and you’re one step closer to that offer. Now go practice!

? Final Notes

• Practice Variations:
• LeetCode 74 (Basic)
• LeetCode 240 (Medium)
• LeetCode 378 (Kth Smallest in Sorted Matrix)
• Key Insight: Reduce 2D search to 1D whenever possible.
• Time: If you see a sorted matrix, binary search or staircase search is almost always the answer.

Now go crush that interview! ?