Search in 2D Matrix in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind searching in a 2D matrix where each row and column is sorted?

Start from the top-right corner and move left if the current number is greater than the target, or move down if it is smaller. This way, you eliminate a row or a column each step.

beginner

Why is starting from the top-right corner effective for searching in a sorted 2D matrix?

Because from the top-right corner, moving left decreases the value and moving down increases the value, allowing a clear decision to move closer to the target.

intermediate

What is the time complexity of searching in a sorted 2D matrix using the top-right corner approach?

O(m + n), where m is the number of rows and n is the number of columns, because each step moves either one row down or one column left.

beginner

Given the matrix: [[1, 4, 7], [2, 5, 8], [3, 6, 9]] What will be the path to find target 5 using the top-right corner search?

Start at 7 (top-right), 7 > 5 so move left to 4, 4 < 5 so move down to 5, found target.

beginner

What happens if the target is not found in the 2D matrix using the top-right corner search method?

The search ends when the indices go out of bounds (row index exceeds number of rows or column index becomes negative), meaning the target is not present.

Where do you start searching in a sorted 2D matrix to efficiently find a target?

A Bottom-left corner

B Top-right corner

C Top-left corner

D Bottom-right corner

Starting at the top-right corner allows moving left or down to eliminate rows or columns efficiently.

If the current number is greater than the target in the top-right corner search, what is the next move?

A Move left

B Move up

C Move right

D Move down

Moving left decreases the number, helping to get closer to the target.

What is the time complexity of the top-right corner search in a matrix with m rows and n columns?

A O(m + n)

B O(m * n)

C O(log(m * n))

D O(1)

Each step moves either one row down or one column left, so total steps are at most m + n.

If the target is smaller than the current number at top-right corner, what direction do you move?

A Right

B Down

C Left

D Up

Moving left decreases the number, which helps find smaller targets.

What condition ends the search when the target is not found?

A When the target is found

B After checking half the matrix

C After a fixed number of steps

D When indices go out of matrix bounds

The search ends when the row index exceeds the number of rows or the column index becomes negative.

Explain the step-by-step process of searching for a target in a 2D matrix sorted by rows and columns using the top-right corner approach.

Think about how moving left or down helps narrow the search.

Describe why the time complexity of searching in a sorted 2D matrix using the top-right corner method is O(m + n).

Consider how many moves you can make before going out of bounds.

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