Search in 2D Matrix in DSA C# - Execution Trace

Concept Flow - Search in 2D Matrix

Start at top-right corner

↓

Compare target with current element

↓

Move left

↓

Repeat until found or out of bounds

↓

Return result

Start searching from the top-right corner. Move left if target is smaller, move down if target is larger, repeat until found or out of bounds.

Execution Sample

DSA C#

int row = 0;
int col = matrix[0].Length - 1;
while (row < matrix.Length && col >= 0) {
  if (matrix[row][col] == target) return true;
  else if (matrix[row][col] > target) col--;
  else row++;
}
return false;

Searches for target in a sorted 2D matrix by moving left or down starting from top-right.

Execution Table

Step	Operation	Current Position (row,col)	Current Element	Comparison with Target	Pointer Change	Visual State
1	Start	(0,4)	15	15 > 5	Move left to (0,3)	[1, 4, 7, 11, 15] [2, 5, 8, 12, 19] [3, 6, 9, 16, 22] [10,13,14,17,24] [18,21,23,26,30]
2	Compare	(0,3)	11	11 > 5	Move left to (0,2)	[1, 4, 7, 11, 15] [2, 5, 8, 12, 19] [3, 6, 9, 16, 22] [10,13,14,17,24] [18,21,23,26,30]
3	Compare	(0,2)	7	7 > 5	Move left to (0,1)	[1, 4, 7, 11, 15] [2, 5, 8, 12, 19] [3, 6, 9, 16, 22] [10,13,14,17,24] [18,21,23,26,30]
4	Compare	(0,1)	4	4 < 5	Move down to (1,1)	[1, 4, 7, 11, 15] [2, 5, 8, 12, 19] [3, 6, 9, 16, 22] [10,13,14,17,24] [18,21,23,26,30]
5	Compare	(1,1)	5	5 == 5	Found target	[1, 4, 7, 11, 15] [2, 5, 8, 12, 19] [3, 6, 9, 16, 22] [10,13,14,17,24] [18,21,23,26,30]

💡 Target found at position (1,1) with value 5.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5
row	0	0	0	0	1	1
col	4	3	2	1	1	1
current_element	15	11	7	4	5	5

Key Moments - 3 Insights

Why do we start searching from the top-right corner?

Because from the top-right, moving left decreases values and moving down increases values, allowing efficient elimination of rows or columns as shown in steps 1-4 in the execution_table.

What happens if the current element is greater than the target?

We move left to a smaller element, as seen in steps 1-3 where the column index decreases to find smaller values.

Why do we move down when the current element is less than the target?

Because moving down leads to larger values, increasing the chance to find the target, demonstrated in step 4 where row increases.

Visual Quiz - 3 Questions

Look at the execution_table, what is the current element at step 3?

A 11

B 4

C 7

D 5

💡 Hint

Check the 'Current Element' column in row for step 3 in execution_table.

At which step does the algorithm move down for the first time?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look at the 'Pointer Change' column to see when row increases.

If the target was 20, how would the pointer move after step 5?

A Move left

B Move down

C Stay in place

D Return found

💡 Hint

Compare target 20 with current element 5 at step 5 and check pointer movement rules.

Concept Snapshot

Search in 2D Matrix:
- Start at top-right corner (row=0, col=last)
- Compare target with current element
- If target < element, move left (col--)
- If target > element, move down (row++)
- Repeat until found or out of bounds
- Efficient for matrices sorted row-wise and column-wise

Full Transcript

This visualization shows how to search a target number in a 2D matrix sorted by rows and columns. We start at the top-right corner. If the current number is bigger than the target, we move left to smaller numbers. If smaller, we move down to bigger numbers. We repeat this until we find the target or run out of matrix. The execution table tracks each step, showing position, current number, comparison, and pointer moves. The variable tracker shows how row and column indexes change. Key moments clarify why we start top-right and how pointer moves depend on comparisons. The quiz tests understanding of these steps. This method is efficient because it eliminates a row or column each step.

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