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 a sorted 2D matrix?

DSA C

#include <stdio.h>
#include <stdbool.h>

bool searchMatrix(int matrix[][4], int rows, int cols, int target) {
    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;
}

int main() {
    int matrix[3][4] = {
        {1, 3, 5, 7},
        {10, 11, 16, 20},
        {23, 30, 34, 60}
    };
    bool found = searchMatrix(matrix, 3, 4, 5);
    printf("%s\n", found ? "true" : "false");
    return 0;
}

A Runtime error

B false

C true

D Compilation error

💡 Hint

Trace the search starting from top-right corner comparing with target 5.

The code starts at the top-right element (7). Since 7 > 5, it moves left to 5, which matches the target. So it returns true.

❓ Predict Output

intermediate

Output when target is not in matrix

What does the following C code print when searching for target 13 in the given 2D matrix?

DSA C

#include <stdio.h>
#include <stdbool.h>

bool searchMatrix(int matrix[][3], int rows, int cols, int target) {
    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;
}

int main() {
    int matrix[3][3] = {
        {1, 4, 7},
        {8, 10, 12},
        {13, 14, 16}
    };
    bool found = searchMatrix(matrix, 3, 3, 13);
    printf("%s\n", found ? "true" : "false");
    return 0;
}

A true

B false

C Compilation error

D Runtime error

💡 Hint

Check if 13 exists in the matrix.

13 is present at matrix[2][0], so the function returns true and prints "true".

❓ Predict Output

advanced

Output of search in non-square matrix

What is the output of this C code searching for target 15 in a 3x5 matrix?

DSA C

#include <stdio.h>
#include <stdbool.h>

bool searchMatrix(int matrix[][5], int rows, int cols, int target) {
    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;
}

int main() {
    int matrix[3][5] = {
        {1, 3, 5, 7, 9},
        {10, 11, 12, 13, 14},
        {15, 16, 17, 18, 19}
    };
    bool found = searchMatrix(matrix, 3, 5, 15);
    printf("%s\n", found ? "true" : "false");
    return 0;
}

A false

B Runtime error

C Compilation error

D true

💡 Hint

Look for 15 in the last row, first column.

15 is found at matrix[2][0], so the function returns true and prints "true".

❓ Predict Output

advanced

Output when target is smaller than all elements

What does this C code print when searching for target 0 in the matrix?

DSA C

#include <stdio.h>
#include <stdbool.h>

bool searchMatrix(int matrix[][3], int rows, int cols, int target) {
    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;
}

int main() {
    int matrix[3][3] = {
        {5, 6, 7},
        {8, 9, 10},
        {11, 12, 13}
    };
    bool found = searchMatrix(matrix, 3, 3, 0);
    printf("%s\n", found ? "true" : "false");
    return 0;
}

A true

B false

C Compilation error

D Runtime error

💡 Hint

Target 0 is less than all matrix elements.

Since 0 is smaller than all elements, the search moves left until column < 0 and returns false.

🧠 Conceptual

expert

Time complexity of search in sorted 2D matrix

What is the time complexity of searching a target in an m x n matrix where each row and column is sorted ascending, using the top-right corner search method?

A O(m + n)

B O(m * n)

C O(log(m * n))

D O(max(m, n) * log(min(m, n)))

💡 Hint

Each step moves either one row down or one column left.

The search starts at top-right and moves at most m times down and n times left, so total steps are O(m + n).

Practice

1. What is the main idea behind searching a target value in a 2D matrix where each row is sorted and the first integer of each row is greater than the last integer of the previous row?

easy

A. Start from bottom-left corner and move up or right

B. Search each row linearly until the target is found

C. Use a hash map to store all elements for quick lookup

D. Treat the 2D matrix as a sorted 1D array and apply binary search

Solution

1. Step 1: Understand matrix sorting property

   Each row is sorted and the first element of a row is greater than the last element of the previous row, so the entire matrix can be seen as a sorted list.

2. Step 2: Apply binary search on the matrix

   By treating the matrix as a single sorted array, binary search can be used efficiently to find the target.

3. Final Answer:

   Treat the 2D matrix as a sorted 1D array and apply binary search -> Option D

4. Quick Check:

   Matrix sorted row-wise = binary search [OK]

Hint: Think of the matrix as one sorted list for binary search [OK]

Common Mistakes:

• Searching each row linearly wastes time
• Using hash map wastes extra space
• Starting from bottom-left only works if columns are sorted

2. Which of the following C code snippets correctly calculates the middle element index when performing binary search on a 2D matrix with rows and columns?

easy

A. int mid = (low + high) / 2; int row = mid % rows; int col = mid / cols;

B. int mid = (low + high) / 2; int row = mid / cols; int col = mid % cols;

C. int mid = (low + high) >> 1; int row = mid % cols; int col = mid / rows;

D. int mid = (low + high) / 2; int row = mid / rows; int col = mid % rows;

Solution

1. Step 1: Calculate mid index in 1D

   mid = (low + high) / 2 correctly finds the middle index between low and high.

2. Step 2: Convert mid to 2D indices

   Row is mid divided by number of columns (mid / cols), column is mid modulo number of columns (mid % cols).

3. Final Answer:

   int mid = (low + high) / 2; int row = mid / cols; int col = mid % cols; -> Option B

4. Quick Check:

   Row = mid/cols, Col = mid%cols [OK]

Hint: Divide mid by cols for row, modulo cols for column [OK]

Common Mistakes:

• Swapping rows and columns in calculation
• Using rows instead of cols for division/modulo
• Using bit shift incorrectly for mid

3. What will be the output of the following C code snippet searching for target 5 in the matrix?

int matrix[3][4] = {
  {1, 3, 5, 7},
  {10, 11, 16, 20},
  {23, 30, 34, 60}
};
int target = 5;
int rows = 3, cols = 4;
int low = 0, high = rows * cols - 1;
int found = 0;
while (low <= high) {
  int mid = (low + high) / 2;
  int r = mid / cols;
  int c = mid % cols;
  if (matrix[r][c] == target) {
    found = 1;
    break;
  } else if (matrix[r][c] < target) {
    low = mid + 1;
  } else {
    high = mid - 1;
  }
}
printf("%d\n", found);

medium

A. 1

B. 0

C. 5

D. Compilation error

Solution

1. Step 1: Perform binary search on matrix

   The code treats the matrix as a sorted 1D array and searches for target 5 using binary search.

2. Step 2: Check if target 5 exists

   5 is present at matrix[0][2], so found will be set to 1 and loop breaks.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   Target found = 1 [OK]

Hint: Binary search returns 1 if target found, else 0 [OK]

Common Mistakes:

• Confusing indices calculation for row and column
• Not updating low and high correctly
• Printing target value instead of found flag

4. Identify the bug in the following C code snippet that searches for a target in a 2D matrix and suggest the fix:

int matrix[2][3] = {{1, 2, 3}, {4, 5, 6}};
int target = 4;
int rows = 2, cols = 3;
int low = 0, high = rows * cols - 1;
int found = 0;
while (low < high) {
  int mid = (low + high) / 2;
  int r = mid / cols;
  int c = mid % cols;
  if (matrix[r][c] == target) {
    found = 1;
    break;
  } else if (matrix[r][c] < target) {
    low = mid + 1;
  } else {
    high = mid - 1;
  }
}
printf("%d\n", found);

medium

A. Change mid calculation to (low + high + 1) / 2

B. Swap row and column calculation

C. Change while condition to low <= high

D. Initialize found to -1 instead of 0

Solution

1. Step 1: Analyze loop condition

   The loop uses while (low < high), which misses the case when low == high, possibly skipping the last element.

2. Step 2: Fix loop condition

   Changing to while (low <= high) ensures all elements are checked, including when low equals high.

3. Final Answer:

   Change while condition to low <= high -> Option C

4. Quick Check:

   Loop must check low == high [OK]

Hint: Use while(low <= high) for complete binary search [OK]

Common Mistakes:

• Using < instead of <= in loop condition
• Incorrect mid calculation causing infinite loop
• Swapping row and column indices

5. Given a 2D matrix where each row and each column is sorted in ascending order, but the first integer of each row is NOT necessarily greater than the last integer of the previous row, which approach is best to search for a target value efficiently?

hard

A. Start from top-right corner and move left or down

B. Search each row using binary search separately

C. Use binary search treating matrix as 1D sorted array

D. Use linear search over all elements

Solution

1. Step 1: Understand matrix property

   Rows are sorted but no guarantee about relation between rows, so matrix is not fully sorted as 1D array.

2. Step 2: Choose search method

   Starting from top-right corner, move left if current > target, move down if current < target, efficiently narrows search.

3. Final Answer:

   Start from top-right corner and move left or down -> Option A

4. Quick Check:

   Partial row sorting = stair-step search [OK]

Hint: Use stair-step search from top-right for partially sorted matrix [OK]

Common Mistakes:

• Applying full binary search on unsorted matrix
• Searching each row linearly wasting time
• Using hash map wasting extra space