Search in 2D Matrix in DSA C# - Time & Space Complexity

Time Complexity: Search in 2D Matrix

O(m x n)

Understanding Time Complexity

We want to understand how long it takes to find a number in a 2D matrix.

How does the search time change when the matrix gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public bool SearchMatrix(int[][] matrix, int target) {
    int rows = matrix.Length;
    int cols = matrix[0].Length;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] == target) {
                return true;
            }
        }
    }
    return false;
}
    

This code looks through each element in the matrix to find the target number.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each element in the matrix.
• How many times: The outer loop runs once for each row, and the inner loop runs once for each column, so total checks = rows x columns.

How Execution Grows With Input

As the matrix size grows, the number of checks grows with the total number of elements.

Input Size (rows x cols)	Approx. Operations
10 x 10 = 100	100 checks
100 x 100 = 10,000	10,000 checks
1000 x 1000 = 1,000,000	1,000,000 checks

Pattern observation: The operations grow proportionally to the total number of elements.

Final Time Complexity

Time Complexity: O(m x n)

This means the time to search grows directly with the number of rows times columns in the matrix.

Common Mistake

[X] Wrong: "Since the matrix is sorted, we can find the target in constant time."

[OK] Correct: Even if rows and columns are sorted, checking each element one by one still takes time proportional to the total elements unless a better search method is used.

Interview Connect

Understanding how search time grows in a matrix helps you explain and improve solutions in real problems, showing you know how to handle data size changes.

Self-Check

"What if the matrix rows and columns are sorted, and we use a binary search approach on each row? How would the time complexity change?"

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