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 or bottom-left corner and move left or down based on comparison with the target to efficiently find the element.

beginner

In a sorted 2D matrix, why is starting from the top-right corner effective for search?

Because from the top-right corner, moving left decreases values and moving down increases values, helping to eliminate rows or columns quickly.

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.

intermediate

Show the C# code snippet to search for a target in a sorted 2D matrix using the top-right corner approach.

int rows = matrix.Length; int cols = matrix[0].Length; int r = 0, c = cols - 1; while (r < rows && c >= 0) { if (matrix[r][c] == target) return true; else if (matrix[r][c] > target) c--; else r++; } return false;

beginner

What happens if the target is smaller than the current element in the top-right corner search?

You move left to the previous column because all elements below are larger, so the target can only be to the left.

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

A Top-right corner

B Top-left corner

C Bottom-right corner

D Center of the matrix

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 search?

A Move left

B Move down

C Move right

D Move up

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

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

A O(m * n)

B O(1)

C O(log(m * n))

D O(m + n)

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

If the current element is less than the target, what should you do next?

A Move left

B Move up

C Move down

D Move right

Moving down increases the element value, searching for larger values closer to the target.

Which of these is NOT a valid step in the top-right corner search algorithm?

A Move left if current > target

B Move right if current < target

C Move down if current < target

D Return true if current == target

Moving right is not used because it would increase the column index beyond the matrix bounds.

Explain how to search for a target value in a 2D matrix where each row and column is sorted.

Think about how moving left or down changes the values.

Describe the time complexity and why the top-right corner search method is efficient for sorted 2D matrices.

Consider how many steps maximum the search takes.

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. Start from the top-right corner and move left or down based on comparison

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

C. Search each row completely using linear search

D. Use binary search on each column independently

Solution

1. Step 1: Understand matrix sorting property

   Each row and column is sorted ascending, so top-right is smallest in column and largest in row.

2. Step 2: Use top-right start to decide movement

   If target is less than current, move left; if greater, move down to find target efficiently.

3. Final Answer:

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

4. Quick Check:

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

Hint: Start search at top-right corner for sorted 2D matrix [OK]

Common Mistakes:

• Starting from bottom-left corner without reason
• Searching each row fully ignoring sorting
• Applying binary search on columns only

2. Which of the following is the correct C# syntax to declare a 2D integer array named matrix with 3 rows and 4 columns?

easy

A. int matrix = new int[3,4];

B. int[,] matrix = new int[3,4];

C. int matrix[3,4];

D. int[][] matrix = new int[3][4];

Solution

1. Step 1: Understand C# 2D array declaration

   In C#, multidimensional arrays use comma inside brackets: int[,] for 2D arrays.

2. Step 2: Check syntax correctness

   int[,] matrix = new int[3,4]; uses correct syntax. Options A, B, C are invalid syntax.

3. Final Answer:

   int[,] matrix = new int[3,4]; -> Option B

4. Quick Check:

   Correct 2D array syntax = int[,] matrix = new int[3,4]; [OK]

Hint: Use int[,] for 2D arrays in C# [OK]

Common Mistakes:

• Using jagged array syntax with wrong initialization
• Trying to declare array without new keyword
• Using incorrect brackets or missing commas

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

int[,] matrix = {
  {1, 3, 5},
  {7, 9, 11},
  {13, 15, 17}
};
int target = 9;
bool found = false;
int row = 0, col = 2;
while (row < 3 && col >= 0) {
  if (matrix[row, col] == target) {
    found = true;
    break;
  } else if (matrix[row, col] > target) {
    col--;
  } else {
    row++;
  }
}
Console.WriteLine(found);

medium

A. false

B. Runtime exception

C. Compilation error

D. true

Solution

1. Step 1: Trace the search starting at (0,2)

   Start at matrix[0,2] = 5. 5 < 9, so move down (row++).

2. Step 2: Move to (1,2) and compare

   matrix[1,2] = 11. 11 > 9, so move left (col--).

3. Step 3: Move to (1,1) and compare

   matrix[1,1] = 9 equals target, set found = true and break loop.

4. Final Answer:

   true -> Option D

5. Quick Check:

   Target found = true [OK]

Hint: Start top-right, move left/down comparing target [OK]

Common Mistakes:

• Confusing row and column indices
• Not updating row or col correctly
• Assuming linear search instead of optimized

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

int[,] matrix = {
  {1, 4, 7},
  {2, 5, 8},
  {3, 6, 9}
};
int target = 5;
int row = 0, col = 0;
bool found = false;
while (row < 3 && col < 3) {
  if (matrix[row, col] == target) {
    found = true;
    break;
  } else if (matrix[row, col] < target) {
    col++;
  } else {
    row++;
  }
}
Console.WriteLine(found);

medium

A. Starting point should be top-right, not top-left

B. Loop condition should use OR instead of AND

C. Should increment row when element is less than target

D. No error, code works correctly

Solution

1. Step 1: Check starting point for search

   Code starts at top-left (0,0), but matrix sorted rows and columns require top-right start for correct search.

2. Step 2: Understand movement logic

   Moving right or down from top-left does not guarantee finding target efficiently or correctly.

3. Final Answer:

   Starting point should be top-right, not top-left -> Option A

4. Quick Check:

   Correct start point = top-right [OK]

Hint: Start search at top-right corner, not top-left [OK]

Common Mistakes:

• Starting search at wrong corner
• Using wrong loop conditions
• Incorrect movement directions

5. Given a 2D matrix where each row and column is sorted ascending, write a method to count how many times a target number appears. Which approach is most efficient?

hard

A. Traverse entire matrix and count matches (O(m*n))

B. Use binary search on each row separately (O(m*log n))

C. Start from top-right and move left/down counting matches (O(m+n))

D. Use hash map to store counts before searching (O(m*n))

Solution

1. Step 1: Analyze brute force approach

   Traversing entire matrix is simple but slow (O(m*n)).

2. Step 2: Consider optimized search from top-right

   Starting at top-right, move left/down to find all occurrences efficiently in O(m+n) time.

3. Step 3: Compare with binary search per row

   Binary search per row is better than brute force but slower than top-right approach.

4. Final Answer:

   Start from top-right and move left/down counting matches (O(m+n)) -> Option C

5. Quick Check:

   Efficient count = top-right search O(m+n) [OK]

Hint: Count matches by top-right search moving left/down [OK]

Common Mistakes:

• Using full matrix traversal ignoring sorting
• Applying binary search without combining results
• Using extra space unnecessarily