Search in 2D Matrix in DSA C++

Mental Model

We look for a number in a grid where each row and column is sorted, by moving step-by-step to narrow down where the number can be.

Analogy: Imagine searching for a book in a library where shelves are sorted by title from left to right and top to bottom. You start at the top-right corner and decide to move left or down depending on the book title you want.

Matrix example:
1  4  7  11
2  5  8  12
3  6  9  16
10 13 14 17
Start at top-right (11):
1  4  7  [11↑]
2  5  8  12
3  6  9  16
10 13 14 17

Dry Run Walkthrough

Input: matrix = [[1,4,7,11],[2,5,8,12],[3,6,9,16],[10,13,14,17]], target = 5

Goal: Find if 5 exists in the matrix

Step 1: Start at top-right element (11)

1  4  7  [11↑]
2  5  8  12
3  6  9  16
10 13 14 17

Why: We start here because it helps decide whether to move left or down

Step 2: Compare 11 with 5, since 11 > 5, move left

1  4  [7↑] 11
2  5  8  12
3  6  9  16
10 13 14 17

Why: Moving left goes to smaller numbers to find target

Step 3: Compare 7 with 5, since 7 > 5, move left

1  [4↑] 7  11
2  5  8  12
3  6  9  16
10 13 14 17

Why: Still too big, keep moving left

Step 4: Compare 4 with 5, since 4 < 5, move down

1  4  7  11
2  [5↑] 8  12
3  6  9  16
10 13 14 17

Why: Moving down goes to bigger numbers to find target

Step 5: Compare 5 with 5, found target

1  4  7  11
2  [5↑] 8  12
3  6  9  16
10 13 14 17

Why: Target found, stop search

Result:

1  4  7  11
2  [5] 8  12
3  6  9  16
10 13 14 17
Answer: true

Annotated Code

DSA C++

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

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int rows = matrix.size();
        if (rows == 0) return false;
        int cols = matrix[0].size();
        int r = 0, c = cols - 1; // start top-right
        while (r < rows && c >= 0) {
            if (matrix[r][c] == target) {
                return true; // found target
            } else if (matrix[r][c] > target) {
                c--; // move left
            } else {
                r++; // move down
            }
        }
        return false; // not found
    }
};

int main() {
    vector<vector<int>> matrix = {
        {1, 4, 7, 11},
        {2, 5, 8, 12},
        {3, 6, 9, 16},
        {10, 13, 14, 17}
    };
    int target = 5;
    Solution sol;
    bool found = sol.searchMatrix(matrix, target);
    cout << (found ? "true" : "false") << endl;
    return 0;
}

int r = 0, c = cols - 1; // start top-right

initialize pointers at top-right corner to begin search

while (r < rows && c >= 0) {

loop while pointers are inside matrix bounds

if (matrix[r][c] == target) {

check if current element is target

return true; // found target

stop search immediately when target found

else if (matrix[r][c] > target) {

if current element is bigger, move left to smaller elements

c--; // move left

decrement column to move left

else {

if current element is smaller, move down to bigger elements

r++; // move down

increment row to move down

Output

true

Complexity Analysis

Time: O(m + n) because we move at most m times down and n times left in the matrix

Space: O(1) because we use only a few variables for pointers, no extra space

vs Alternative: Compared to searching every element O(m*n), this approach is much faster by skipping impossible areas

Edge Cases

empty matrix

returns false immediately because no elements to search

DSA C++

if (rows == 0) return false;

target smaller than smallest element

search moves left until out of bounds and returns false

DSA C++

while (r < rows && c >= 0)

target larger than largest element

search moves down until out of bounds and returns false

DSA C++

while (r < rows && c >= 0)

When to Use This Pattern

When you see a sorted 2D matrix and need to find a number quickly, use the top-right corner search pattern to eliminate rows or columns step-by-step.

Common Mistakes

Mistake: Starting search from top-left or bottom-left which doesn't allow easy elimination of rows or columns
Fix: Always start from top-right corner to decide moving left or down

Mistake: Not checking matrix empty condition leading to runtime errors
Fix: Add check for empty matrix before starting search

Summary

Searches a sorted 2D matrix for a target by moving left or down from top-right corner.

Use when matrix rows and columns are sorted and you want efficient search.

Start at top-right and move left if too big, down if too small to quickly find target or conclude absence.