Search in 2D Matrix in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the target is equal to the current matrix element.

DSA Java

if(matrix[i][j] [1] target) {
    return true;
}

Drag options to blanks, or click blank then click option'

A==

B=

C!=

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '=' instead of '==' causes assignment, not comparison.

Using '!=' will check for inequality, which is not what we want here.

Use '==' to compare values in Java. '=' is for assignment.

2fill in blank

medium

Complete the code to move to the next row when the target is greater than the last element in the current row.

DSA Java

if(target > matrix[i][matrix[i].[1] - 1]) {
    i++;
    j = 0;
}

Drag options to blanks, or click blank then click option'

A0

Bsize

Clength()

Dlength

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'length()' which is for Strings, not arrays.

Using 'size' which is for collections, not arrays.

Use 'length' to get the number of columns in a 2D array in Java.

3fill in blank

hard

Fix the error in the loop condition to iterate over all rows of the matrix.

DSA Java

for(int i = 0; i [1] matrix.length; i++) {
    // loop body
}

Drag options to blanks, or click blank then click option'

A<

B>

C>=

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>=' or '>' will not start the loop correctly.

Using '<=' causes the loop to run one extra time.

Use '<' to iterate from 0 up to but not including matrix.length.

4fill in blank

hard

Fill both blanks to correctly implement binary search on a sorted row.

DSA Java

int left = 0, right = matrix[[1]].[2] - 1;
while(left <= right) {
    int mid = left + (right - left) / 2;
    if(matrix[row][mid] == target) return true;
    else if(matrix[row][mid] < target) left = mid + 1;
    else right = mid - 1;
}

Drag options to blanks, or click blank then click option'

Arow

Blength

Clength()

Dsize

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'length()' or 'size' which are invalid for arrays.

Using wrong variable instead of 'row' for the row index.

Use 'row' as the index for the current row and 'length' to get the number of columns.

5fill in blank

hard

Fill both blanks to complete the method that searches the matrix for the target using binary search on each row.

DSA Java

public boolean searchMatrix(int[][] matrix, int target) {
    for(int [1] = 0; [1] < matrix.length; [1]++) {
        int left = 0, right = matrix[[1]].[2] - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(matrix[[1]][mid] == target) return true;
            else if(matrix[[1]][mid] < target) left = mid + 1;
            else right = mid - 1;
        }
    }
    return false;
}

Drag options to blanks, or click blank then click option'

Ai

Blength

Clength()

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'j' as loop variable for rows is confusing.

Using 'length()' or 'size' instead of 'length' for arrays.

Use 'i' as the loop variable and row index, and 'length' to get the number of columns.

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