Search in 2D Matrix in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of search in sorted 2D matrix

What is the output of the following C# code that searches for the target 5 in the given 2D matrix?

DSA C#

int[][] matrix = new int[][] {
    new int[] {1, 3, 5, 7},
    new int[] {10, 11, 16, 20},
    new int[] {23, 30, 34, 50}
};
int target = 5;

bool SearchMatrix(int[][] mat, int t) {
    int rows = mat.Length;
    int cols = mat[0].Length;
    int left = 0, right = rows * cols - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        int midValue = mat[mid / cols][mid % cols];
        if (midValue == t) return true;
        else if (midValue < t) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

Console.WriteLine(SearchMatrix(matrix, target));

A True

B False

C Compilation error

D Runtime exception

💡 Hint

Think about how the matrix is treated as a sorted list for binary search.

The code treats the 2D matrix as a sorted 1D array by calculating mid index and accessing elements using division and modulo. Since 5 is present in the matrix, the search returns true.

❓ Predict Output

intermediate

Output when target is not in matrix

What will be the output of this C# code searching for target 13 in the 2D matrix?

DSA C#

int[][] matrix = new int[][] {
    new int[] {1, 3, 5, 7},
    new int[] {10, 11, 16, 20},
    new int[] {23, 30, 34, 50}
};
int target = 13;

bool SearchMatrix(int[][] mat, int t) {
    int rows = mat.Length;
    int cols = mat[0].Length;
    int left = 0, right = rows * cols - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        int midValue = mat[mid / cols][mid % cols];
        if (midValue == t) return true;
        else if (midValue < t) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

Console.WriteLine(SearchMatrix(matrix, target));

A False

B True

C IndexOutOfRangeException

D Compilation error

💡 Hint

Check if 13 exists in the matrix.

The target 13 is not present in the matrix, so the binary search completes without finding it and returns false.

🔧 Debug

advanced

Identify the error in matrix search code

What error will this C# code produce when searching for target 7 in the matrix?

DSA C#

int[][] matrix = new int[][] {
    new int[] {1, 2, 3},
    new int[] {4, 5, 6}
};
int target = 7;

bool SearchMatrix(int[][] mat, int t) {
    int rows = mat.Length;
    int cols = mat[0].Length;
    int left = 0, right = rows * cols - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        int midValue = mat[mid / cols][mid % cols];
        if (midValue == t) return true;
        else if (midValue < t) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

Console.WriteLine(SearchMatrix(matrix, target));

A Compilation error

B False

C True

D IndexOutOfRangeException

💡 Hint

Check the calculation of right boundary.

The right boundary is set to rows * cols instead of rows * cols - 1, causing mid to go out of range and throw IndexOutOfRangeException.

🧠 Conceptual

advanced

Why binary search works on this 2D matrix

Why can we apply binary search on this 2D matrix as if it were a sorted 1D array?

A Because all elements are unique

B Because the matrix is square

C Because each row is sorted and the first element of each row is greater than the last element of the previous row

D Because the matrix has equal number of rows and columns

💡 Hint

Think about the order of elements across rows.

Binary search works because the matrix is sorted row-wise and each row's first element is greater than the last element of the previous row, making the entire matrix sorted if flattened.

❓ Predict Output

expert

Output of search with duplicate elements in matrix

What is the output of this C# code searching for target 3 in a matrix with duplicates?

DSA C#

int[][] matrix = new int[][] {
    new int[] {1, 2, 3, 3},
    new int[] {4, 5, 6, 7},
    new int[] {8, 9, 10, 11}
};
int target = 3;

bool SearchMatrix(int[][] mat, int t) {
    int rows = mat.Length;
    int cols = mat[0].Length;
    int left = 0, right = rows * cols - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        int midValue = mat[mid / cols][mid % cols];
        if (midValue == t) return true;
        else if (midValue < t) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

Console.WriteLine(SearchMatrix(matrix, target));

A False

B True

C IndexOutOfRangeException

D Compilation error

💡 Hint

Duplicates do not affect binary search correctness if matrix is sorted.

The binary search finds the target 3 even if it appears multiple times, returning true.

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