Search in 2D Matrix in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of search in sorted 2D matrix

What is the output of the following Java code that searches for the number 5 in a sorted 2D matrix?

DSA Java

public class SearchMatrix {
    public static boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        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;
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 3, 5, 7},
            {10, 11, 16, 20},
            {23, 30, 34, 50}
        };
        System.out.println(searchMatrix(matrix, 5));
    }
}

A Runtime exception

B false

C Compilation error

D true

💡 Hint

The search starts from top-right corner and moves left or down based on comparison.

The code correctly implements a search in a sorted 2D matrix by starting at the top-right corner and moving left if the current element is greater than target or down if smaller. Since 5 is present, it returns true.

❓ Predict Output

intermediate

Output when target is not in matrix

What will be the output of this code when searching for 13 in the same matrix?

DSA Java

public class SearchMatrix {
    public static boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        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;
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 3, 5, 7},
            {10, 11, 16, 20},
            {23, 30, 34, 50}
        };
        System.out.println(searchMatrix(matrix, 13));
    }
}

A true

B Compilation error

C false

D Runtime exception

💡 Hint

Check if 13 exists in the matrix by following the search path.

The search moves through the matrix but does not find 13, so it returns false.

🔧 Debug

advanced

Identify the error in matrix search code

What error does this code produce when run, and why?

DSA Java

public class SearchMatrix {
    public static boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        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;
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 3, 5, 7},
            {10, 11, 16, 20},
            {23, 30, 34, 50}
        };
        System.out.println(searchMatrix(matrix, 100));
    }
}

A ArrayIndexOutOfBoundsException because loop condition allows r == rows

B NullPointerException due to uninitialized matrix

C Compilation error due to missing semicolon

D No error, prints true

💡 Hint

Check the loop condition for row index boundary.

The loop condition uses r <= rows which allows r to equal rows, causing an index out of bounds when accessing matrix[r][c].

🧠 Conceptual

advanced

Time complexity of search in sorted 2D matrix

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

A O(m + n)

B O(m * n)

C O(log m + log n)

D O(log (m * n))

💡 Hint

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

At most, the search moves m times down and n times left, so total steps are O(m + n).

🚀 Application

expert

Find the number of elements less than or equal to target

Given a sorted 2D matrix (each row and column sorted ascending), which code snippet correctly counts how many elements are less than or equal to a target value?

A

int countLessEqual(int[][] matrix, int target) {
    int count = 0;
    int rows = matrix.length;
    int cols = matrix[0].length;
    int r = rows - 1, c = 0;
    while (r >= 0 && c < cols) {
        if (matrix[r][c] <= target) {
            count += r + 1;
            c++;
        } else {
            r--;
        }
    }
    return count;
}

B

int countLessEqual(int[][] matrix, int target) {
    int count = 0;
    int rows = matrix.length;
    int cols = matrix[0].length;
    int r = 0, c = cols - 1;
    while (r < rows && c >= 0) {
        if (matrix[r][c] <= target) {
            count += c + 1;
            r++;
        } else {
            c--;
        }
    }
    return count;
}

C

int countLessEqual(int[][] matrix, int target) {
    int count = 0;
    int rows = matrix.length;
    int cols = matrix[0].length;
    int r = 0, c = 0;
    while (r < rows && c < cols) {
        if (matrix[r][c] <= target) {
            count++;
            c++;
        } else {
            r++;
        }
    }
    return count;
}

D

int countLessEqual(int[][] matrix, int target) {
    int count = 0;
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] <= target) count++;
        }
    }
    return count;
}

💡 Hint

Use the property of sorted rows and columns to count efficiently from top-right corner.

Starting from top-right, if matrix[r][c] <= target, all elements in that row before c are <= target, so add c+1 and move down. Else move left.

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. Treat the 2D matrix as a sorted 1D array and apply binary search

B. Search each row linearly until the target is found

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

D. Start from the bottom-left corner and move diagonally

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 1D 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 A

4. Quick Check:

   Matrix sorted row-wise = binary search [OK]

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

Common Mistakes:

• Searching each row linearly wastes time
• Using hash map wastes extra space
• Starting from bottom-left only works for different matrix types

2. Which of the following Java code snippets correctly calculates the middle index for binary search on a 2D matrix treated as a 1D array with total elements rows * cols?

easy

A. int mid = (low * high) / 2;

B. int mid = (low + high) / 2;

C. int mid = (low - high) / 2;

D. int mid = low + (high - low) / 2;

Solution

1. Step 1: Understand safe mid calculation

   Using low + (high - low) / 2 prevents integer overflow compared to (low + high) / 2.

2. Step 2: Check other options

   int mid = (low - high) / 2; and D do not correctly calculate mid index for binary search.

3. Final Answer:

   int mid = low + (high - low) / 2; -> Option D

4. Quick Check:

   Safe mid calculation = low + (high - low) / 2 [OK]

Hint: Use low + (high - low) / 2 to avoid overflow [OK]

Common Mistakes:

• Using (low + high) / 2 can cause overflow
• Using subtraction incorrectly for mid
• Multiplying low and high is wrong

3. Given the following Java code to search for target 5 in the matrix int[][] matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};, what will be the output?

public static boolean searchMatrix(int[][] matrix, int target) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int low = 0, high = rows * cols - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        int midValue = matrix[mid / cols][mid % cols];
        if (midValue == target) return true;
        else if (midValue < target) low = mid + 1;
        else high = mid - 1;
    }
    return false;
}

System.out.println(searchMatrix(matrix, 5));

medium

A. true

B. false

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Understand matrix and target

   The matrix contains 5 at position (0,2). The binary search checks mid values correctly by converting 1D mid to 2D indices.

2. Step 2: Trace binary search steps

   Binary search finds 5 and returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   5 found in matrix = true [OK]

Hint: Convert mid to row and col using mid/cols and mid%cols [OK]

Common Mistakes:

• Using wrong index conversion for mid
• Confusing row and column indices
• Returning false before full search

4. Identify the bug in the following Java method that searches a target 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:

public static boolean searchMatrix(int[][] matrix, int target) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int low = 0, high = rows * cols;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        int midValue = matrix[mid / cols][mid % cols];
        if (midValue == target) return true;
        else if (midValue < target) low = mid + 1;
        else high = mid - 1;
    }
    return false;
}

medium

A. The mid calculation causes overflow

B. The high index should be rows * cols - 1, not rows * cols

C. The matrix indexing is incorrect

D. The loop condition should be low < high

Solution

1. Step 1: Check high initialization

   High should be the last valid index, which is rows * cols - 1, not rows * cols (which is out of bounds).

2. Step 2: Verify other parts

   Mid calculation and indexing are correct; loop condition low <= high is standard for binary search.

3. Final Answer:

   The high index should be rows * cols - 1, not rows * cols -> Option B

4. Quick Check:

   High index off by one causes error [OK]

Hint: High index = total elements - 1 for zero-based arrays [OK]

Common Mistakes:

• Setting high to rows * cols causes out-of-bounds
• Changing loop condition incorrectly
• Miscomputing mid index

5. You have a 2D matrix where each row 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. Use binary search treating matrix as 1D sorted array

B. Perform binary search on each row separately

C. Start from top-right corner and move left/down based on comparison

D. Use linear search over all elements

Solution

1. Step 1: Understand matrix property

   Rows are sorted but no guarantee that next row's first element is greater than previous row's last element, so treating as 1D sorted array is invalid.

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/down based on comparison -> Option C

4. Quick Check:

   Top-right corner search = efficient for partially sorted matrix [OK]

Hint: Top-right corner search works when rows sorted but no global order [OK]

Common Mistakes:

• Applying 1D binary search wrongly
• Searching each row fully wastes time
• Using linear search is slow