Search in 2D Matrix in DSA Java - Execution Trace

Concept Flow - Search in 2D Matrix

Start at top-right corner

↓

Compare target with current element

↓

Move left

↓

Found target?

Start from the top-right element, compare with target, move left if target is smaller, move down if larger, repeat until found or out of bounds.

Execution Sample

DSA Java

int row = 0;
int col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
  if (matrix[row][col] == target) return true;
  else if (matrix[row][col] > target) col--;
  else row++;
}
return false;

Search target in sorted 2D matrix by starting at top-right and moving left/down based on comparison.

Execution Table

Step	Operation	Current Position (row,col)	Current Element	Comparison with Target	Action	Visual State
1	Start	(0,4)	15	15 > 5	Move left	[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
2	Compare	(0,3)	11	11 > 5	Move left	[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
3	Compare	(0,2)	7	7 > 5	Move left	[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
4	Compare	(0,1)	4	4 < 5	Move down	[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
5	Compare	(1,1)	5	5 == 5	Found target	[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]

💡 Target 5 found at position (1,1), search ends.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5
row	0	0	0	0	1	1
col	4	3	2	1	1	1
current_element	15	11	7	4	5	5

Key Moments - 3 Insights

Why do we start searching from the top-right corner?

Starting at top-right lets us decide to move left if current element is bigger or down if smaller, efficiently narrowing search. See execution_table steps 1-4.

Why move left when current element is greater than target?

Because rows are sorted ascending left to right, moving left leads to smaller elements. This is shown in steps 1-3 where col decreases.

Why move down when current element is less than target?

Because columns are sorted ascending top to bottom, moving down leads to larger elements. Step 4 shows row increasing when element 4 < target 5.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'col' after step 3?

A 4

B 2

C 1

D 3

💡 Hint

Check variable_tracker row for 'col' after step 3.

At which step does the search move down to the next row?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Action' column in execution_table where 'Move down' occurs.

If the target was 20 instead of 5, what would be the first action at step 1?

A Move left

B Move down

C Found target

D Exit search

💡 Hint

Compare target 20 with current element 15 at position (0,4) in execution_table step 1.

Concept Snapshot

Search in 2D Matrix:
- Start at top-right element (row=0, col=last)
- While inside matrix bounds:
  - If element == target: found
  - If element > target: move left (col--)
  - Else move down (row++)
- Stop when found or out of bounds

Full Transcript

This concept shows how to search a target value in a 2D matrix sorted ascending left to right and top to bottom. We start at the top-right corner. If the current element is bigger than the target, we move left to smaller elements. If smaller, we move down to bigger elements. We repeat until we find the target or go outside the matrix. The execution table traces each step, showing position, element, comparison, and action. Variable tracker shows how row and col change. Key moments clarify why we start top-right and why we move left or down. The visual quiz tests understanding of these steps and decisions.

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