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.

Practice

1. What is the main idea behind searching in a 2D matrix where each row and column is sorted in ascending order?

easy

A. Use binary search on each row independently

B. Start from the top-right corner and move left or down based on comparison

C. Search each element row by row until the target is found

D. Start from the bottom-left corner and move right or up based on comparison

Solution

1. Step 1: Understand matrix properties

   Each row and column is sorted ascending, so top-right element is a good start to decide direction.

2. Step 2: Use top-right corner to guide search

   If target is less than current element, move left; if greater, move down.

3. Final Answer:

   Start from the top-right corner and move left or down based on comparison -> Option B

4. Quick Check:

   Top-right corner search = Start from the top-right corner and move left or down based on comparison [OK]

Hint: Start at top-right, move left/down based on target comparison [OK]

Common Mistakes:

• Starting from bottom-left without adjusting moves
• Searching all elements without using sorting
• Using binary search on unsorted columns

2. Which of the following C++ code snippets correctly initializes a 2D vector matrix with 3 rows and 4 columns filled with zeros?

easy

A. std::vector matrix(4, std::vector<int>(3, 0));

B. std::vector<int> matrix(3, std::vector<int>(4, 0));

C. std::vector matrix(3, std::vector<int>(4, 0));

D. std::vector matrix(3, 4, 0);

Solution

1. Step 1: Understand vector initialization syntax

   To create a 2D vector with 3 rows and 4 columns, use vector of vectors with inner vector size 4.

2. Step 2: Check each option

   std::vector matrix(3, std::vector<int>(4, 0)); correctly uses vector with 3 rows and inner vector of size 4 filled with 0.

3. Final Answer:

   std::vector matrix(3, std::vector<int>(4, 0)); -> Option C

4. Quick Check:

   Correct 2D vector init = std::vector matrix(3, std::vector<int>(4, 0)); [OK]

Hint: Use vector(rows, vector<int>(cols, val)) [OK]

Common Mistakes:

• Using wrong vector type for inner vector
• Swapping rows and columns sizes
• Trying to pass three arguments to vector constructor

3. What will be the output of the following C++ code snippet?

std::vector matrix = {
  {1, 4, 7, 11},
  {2, 5, 8, 12},
  {3, 6, 9, 16},
  {10, 13, 14, 17}
};
int target = 5;
int row = 0, col = 3;
bool found = false;
while (row < 4 && col >= 0) {
  if (matrix[row][col] == target) {
    found = true;
    break;
  } else if (matrix[row][col] > target) {
    col--;
  } else {
    row++;
  }
}
std::cout << (found ? "Found" : "Not Found") << std::endl;

medium

A. Found

B. Not Found

C. Compilation Error

D. Runtime Error

Solution

1. Step 1: Trace the search starting at matrix[0][3]

   matrix[0][3] = 11, target=5, 11 > 5 so col-- to 2.

2. Step 2: Continue search

   matrix[0][2] = 7, 7 > 5 so col-- to 1; matrix[0][1] = 4, 4 < 5 so row++ to 1; matrix[1][1] = 5 equals target, found = true.

3. Final Answer:

   Found -> Option A

4. Quick Check:

   Search finds 5 at (1,1) = Found [OK]

Hint: Start top-right, move left if bigger, down if smaller [OK]

Common Mistakes:

• Not updating row and col correctly
• Confusing comparison operators
• Assuming target not found without full search

4. Identify the bug in the following C++ code that searches for a target in a sorted 2D matrix:

bool searchMatrix(std::vector& matrix, int target) {
  int row = 0, col = matrix[0].size() - 1;
  while (row <= matrix.size() && col >= 0) {
    if (matrix[row][col] == target) return true;
    else if (matrix[row][col] > target) col--;
    else row++;
  }
  return false;
}

medium

A. The while loop condition should use < instead of <= for row

B. The initial column index is incorrect

C. The function should return false inside the loop

D. The matrix should be passed by value, not reference

Solution

1. Step 1: Analyze loop boundary for row index

   matrix.size() gives number of rows; valid row indices are 0 to size()-1, so row < size() is correct.

2. Step 2: Identify off-by-one error

   Using row <= matrix.size() allows row to equal size(), causing out-of-bounds access.

3. Final Answer:

   The while loop condition should use < instead of <= for row -> Option A

4. Quick Check:

   Row index must be less than size() [OK]

Hint: Use < size() for indices, not <= size() [OK]

Common Mistakes:

• Using <= causing out-of-bounds errors
• Incorrect initial column index
• Returning false too early inside loop

5. Given a 2D matrix where each row and column is sorted ascending, write a function to count how many elements are less than or equal to a target value. Which approach is most efficient?

hard

A. Flatten matrix and sort, then count using binary search (O(m*n log(m*n)))

B. Use binary search on each row to find count per row (O(m*log n))

C. Traverse each element and count if <= target (O(m*n))

D. Start from bottom-left and move up or right to count (O(m+n))

Solution

1. Step 1: Understand matrix sorted property

   Rows and columns sorted ascending allows efficient traversal from bottom-left.

2. Step 2: Use bottom-left traversal to count elements

   Start at bottom-left; if element <= target, all elements above in that column are <= target, move right and add count; else move up.

3. Step 3: Compare efficiency

   This approach visits at most m+n elements, better than binary search on each row or full traversal.

4. Final Answer:

   Start from bottom-left and move up or right to count (O(m+n)) -> Option D

5. Quick Check:

   Bottom-left traversal counts in O(m+n) [OK]

Hint: Count using bottom-left traversal for O(m+n) time [OK]

Common Mistakes:

• Using full traversal causing O(m*n) time
• Applying binary search on unsorted columns
• Flattening matrix unnecessarily increasing complexity