Search in 2D Matrix in DSA C#

Mental Model

We look for a number in a grid where each row and column is sorted. We start from a corner and move step by step to find the number or know it is not there.

Analogy: Imagine a library shelf where books are arranged by height from left to right and top to bottom. To find a book of a certain height, you start at the top-right corner and move left if the book is too tall or down if the book is too short.

Matrix:
[1, 3, 5, 7]
[2, 4, 6, 8]
[3, 5, 7, 9]

Start at top-right corner:
1 -> 3 -> 5 -> [7 ↑]
↓    ↓    ↓    ↓
2    4    6    8
↓    ↓    ↓    ↓
3    5    7    9

Dry Run Walkthrough

Input: matrix = [[1,3,5,7],[2,4,6,8],[3,5,7,9]], target = 5

Goal: Find if 5 exists in the matrix and show the path taken

Step 1: Start at top-right corner (row=0, col=3) with value 7

Matrix position: 1 -> 3 -> 5 -> [7 ↑]
                             ↑

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

Step 2: Compare 7 with target 5, 7 > 5, move left to col=2

Matrix position: 1 -> 3 -> [5 ↑] -> 7
                         ↑

Why: Since 7 is bigger than 5, moving left goes to smaller numbers

Step 3: Compare 5 with target 5, found target

Matrix position: 1 -> 3 -> [5 ↑] -> 7
                         ↑

Why: Value matches target, search ends successfully

Result:

Matrix position: 1 -> 3 -> [5 ↑] -> 7
                         ↑
Target 5 found in matrix

Annotated Code

DSA C#

using System;

class Search2DMatrix {
    public static bool SearchMatrix(int[][] matrix, int target) {
        int rows = matrix.Length;
        if (rows == 0) return false;
        int cols = matrix[0].Length;

        int row = 0;
        int col = cols - 1;

        while (row < rows && col >= 0) {
            if (matrix[row][col] == target) {
                return true; // found target
            } else if (matrix[row][col] > target) {
                col--; // move left to smaller values
            } else {
                row++; // move down to larger values
            }
        }
        return false; // target not found
    }

    static void Main() {
        int[][] matrix = new int[][] {
            new int[] {1, 3, 5, 7},
            new int[] {2, 4, 6, 8},
            new int[] {3, 5, 7, 9}
        };
        int target = 5;
        bool found = SearchMatrix(matrix, target);
        Console.WriteLine(found ? "Target 5 found in matrix" : "Target 5 not found in matrix");
    }
}

int row = 0; int col = cols - 1;

start at top-right corner of matrix

while (row < rows && col >= 0) {

loop while inside matrix bounds

if (matrix[row][col] == target) {

check if current value matches target

return true; // found target

stop search when target found

else if (matrix[row][col] > target) { col--; // move left to smaller values }

move left if current value is too big

else { row++; // move down to larger values }

move down if current value is too small

Output

Target 5 found in matrix

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 only use a few variables for row and column indices

vs Alternative: Compared to searching every element (O(m*n)), this method is much faster by skipping unnecessary checks

Edge Cases

Empty matrix

Returns false immediately because there is nothing 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 (row < rows && col >= 0)

Target larger than largest element

Search moves down until out of bounds and returns false

DSA C#

while (row < rows && col >= 0)

When to Use This Pattern

When you see a sorted 2D matrix and need to find a value 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 corner without adjusting moves properly
Fix: Always start from top-right corner and move left or down based on comparison

Mistake: Not checking matrix bounds before accessing elements
Fix: Use while loop conditions to ensure row and col indices stay within matrix limits

Summary

Searches a sorted 2D matrix efficiently by starting at the top-right corner and moving left or down.

Use when the matrix rows and columns are sorted and you want to find if a target exists quickly.

The key insight is that from the top-right corner, you can decide to move left or down to eliminate parts of the matrix.

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