Search in 2D Matrix in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

Start from the top-right corner and move left if the current element is greater than the target, or move down if it is smaller. This way, you eliminate a row or a column in each step.

beginner

Why is starting from the top-right corner effective in searching a sorted 2D matrix?

Because from the top-right corner, moving left decreases the value and moving down increases the value, helping to decide the direction to find the target efficiently.

intermediate

What is the time complexity of searching in a sorted 2D matrix using the top-right corner approach?

O(m + n), where m is the number of rows and n is the number of columns, because each step moves either one row down or one column left.

beginner

In a 2D matrix sorted row-wise and column-wise, what happens if the target is smaller than the current element at top-right?

You move left to the previous column because all elements below are larger, so the target cannot be in the current column.

intermediate

What is a simple alternative approach to search in a 2D matrix if it is treated as a sorted 1D array?

Use binary search by mapping 2D indices to 1D indices, since the matrix is sorted row-wise and column-wise, treating it as a single sorted list.

Where do you start searching in a sorted 2D matrix to efficiently find a target?

A Top-right corner

B Bottom-left corner

C Top-left corner

D Bottom-right corner

Starting at the top-right corner allows moving left or down to eliminate rows or columns efficiently.

If the current element is greater than the target, what is the next move in the top-right corner search?

A Move left

B Move down

C Move right

D Move up

Moving left decreases the element value, helping to find smaller target values.

What is the time complexity of the top-right corner search in a matrix with m rows and n columns?

A O(m * n)

B O(m + n)

C O(log(m * n))

D O(max(m, n))

Each step moves either one row down or one column left, so total steps are at most m + n.

Which of these is NOT true about the 2D matrix search starting at top-right?

A You eliminate one row or column each step

B You move left if current element is greater than target

C You move down if current element is less than target

D You move right if current element is less than target

You never move right in this approach; moving right would increase the element value.

What alternative method can be used if the matrix is sorted and treated as a 1D array?

A Linear search

B Depth-first search

C Binary search

D Breadth-first search

Binary search can be applied by mapping 2D indices to 1D indices in a sorted matrix.

Explain the step-by-step process of searching for a target in a 2D matrix sorted by rows and columns using the top-right corner approach.

Think about how moving left or down helps eliminate parts of the matrix.

Describe how binary search can be applied to a 2D matrix sorted row-wise and column-wise by treating it as a 1D array.

Think about flattening the matrix conceptually without changing the data.

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