Search in 2D Matrix in DSA Javascript - Execution Trace

Concept Flow - Search in 2D Matrix

Start at top-right corner

↓

Compare target with current element

↓

Move left

↓

Check bounds

Yes/No↓

Return result

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 Javascript

function searchMatrix(matrix, target) {
  let row = 0;
  let 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;
}

Searches for target in a sorted 2D matrix by starting at top-right and moving left or down.

Execution Table

Step	Operation	Current Position (row,col)	Current Element	Comparison with Target	Pointer Changes	Visual State
1	Start	(0,4)	15	15 > 5	Move left: col = 3	[[1,3,5,7,15], [10,11,16,20,25], [23,30,34,50,60]]
2	Compare	(0,3)	7	7 > 5	Move left: col = 2	[[1,3,5,7,15], [10,11,16,20,25], [23,30,34,50,60]]
3	Compare	(0,2)	5	5 == 5	Found target	[[1,3,5,7,15], [10,11,16,20,25], [23,30,34,50,60]]
4	Return	-	-	-	-	Target found, search ends

💡 Target found at position (0,2), search stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
row	0	0	0	0	0
col	4	3	2	2	2
current_element	15	7	5	5	5
found	false	false	false	true	true

Key Moments - 3 Insights

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

Because from the top-right, moving left decreases values and moving down increases values, allowing efficient elimination of rows or columns as shown in steps 1 and 2 of the execution_table.

What happens if the current element is greater than the target?

We move left by decreasing the column index, as seen in steps 1 and 2, because all elements below are larger, so moving down would not help.

Why do we stop when the row or column goes out of bounds?

Because it means we have checked all possible positions without finding the target, so the search ends as per the while loop condition in the code.

Visual Quiz - 3 Questions

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

A 2

B 3

C 4

D 1

💡 Hint

Check the 'Pointer Changes' and 'Current Position' columns in step 2 of the execution_table.

At which step does the search find the target?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look for the row where 'Comparison with Target' shows equality in the execution_table.

If the target was 17 instead of 5, what would be the pointer change after step 1?

A Move left: col = 3

B Move down: row = 1

C Found target

D No pointer change

💡 Hint

Recall that if current element is less than target, we move down as per the code and concept_flow.

Concept Snapshot

Search in 2D Matrix:
- Start at top-right element (row=0, col=last)
- Compare element with target
- If element > target, move left (col--)
- If element < target, move down (row++)
- Repeat until found or out of bounds
- Efficient for sorted rows and columns

Full Transcript

This concept shows how to search a target value in a 2D matrix where each row and column is sorted. We start from the top-right corner and compare the current element with the target. If the current element is greater, we move left to smaller elements. If it is smaller, we move down to larger elements. We continue this until we find the target or run out of matrix bounds. The execution table traces each step, showing pointer movements and comparisons. This method efficiently narrows down the search space by eliminating rows or columns at each step.

Practice

1. What is the main idea behind searching a target value in a 2D matrix where each row and column is sorted in ascending order?

easy

A. Use binary search on each row independently

B. Start from bottom-left corner and move right or down based on comparison

C. Search each element one by one from top-left to bottom-right

D. Start from top-right corner and move left or down based on comparison

Solution

1. Step 1: Understand matrix properties

   Each row and column is sorted ascending, so top-right element is a good start to decide direction.

2. Step 2: Use top-right corner to guide search

   If target is less than current element, move left; if greater, move down.

3. Final Answer:

   Start from top-right corner and move left or down based on comparison -> Option D

4. Quick Check:

   Top-right start = efficient search [OK]

Hint: Start at top-right to decide move direction quickly [OK]

Common Mistakes:

• Searching all elements one by one wastes time
• Starting from bottom-left without clear logic
• Using binary search on each row ignores column sorting

2. Which of the following is the correct syntax to check if a target exists in a 2D matrix named matrix in JavaScript?

easy

A. for(let i=0; i

B. for(let i=0; i

C. for(let i=0; i

D. for(let i=0; i

Solution

1. Step 1: Identify correct loop ranges

   Outer loop runs over rows (matrix.length), inner loop over columns (matrix[0].length).

2. Step 2: Check element equality with strict equality

   Use === for exact match and return true if found.

3. Final Answer:

   for(let i=0; i -> Option B

4. Quick Check:

   Correct loop ranges and strict equality [OK]

Hint: Outer loop rows, inner loop columns, use === for comparison [OK]

Common Mistakes:

• Swapping row and column lengths in loops
• Using == instead of === causing type coercion
• Looping inner loop with wrong length causing errors

3. What will be the output of the following code snippet?

const matrix = [
  [1, 4, 7, 11],
  [2, 5, 8, 12],
  [3, 6, 9, 16],
  [10, 13, 14, 17]
];
const target = 5;

function searchMatrix(matrix, target) {
  let row = 0;
  let 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;
}

console.log(searchMatrix(matrix, target));

medium

A. Error

B. false

C. true

D. undefined

Solution

1. Step 1: Start from top-right element

   Initial position is matrix[0][3] = 11, compare with target 5.

2. Step 2: Move left since 11 > 5, now at matrix[0][2] = 7

   7 > 5, move left again to matrix[0][1] = 4.

3. Step 3: 4 < 5, move down to matrix[1][1] = 5

   Found target 5, return true.

4. Final Answer:

   true -> Option C

5. Quick Check:

   Top-right search finds 5 = true [OK]

Hint: Move left if bigger, down if smaller from top-right [OK]

Common Mistakes:

• Starting from wrong corner causing wrong moves
• Not updating row or column correctly
• Returning false too early without full search

4. Find the bug in the following code that searches for a target in a 2D matrix where rows and columns are sorted.

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

medium

A. The directions to move row and col are swapped in conditions

B. The initial row and col values are incorrect

C. The while loop condition should use '||' instead of '&&'

D. The function should return false inside the loop

Solution

1. Step 1: Analyze movement logic

   Starting at bottom-left, if current < target, should move right (col++), else move up (row--).

2. Step 2: Check conditions in code

   Code moves row-- when current < target, which is wrong; it should move col++ instead.

3. Final Answer:

   The directions to move row and col are swapped in conditions -> Option A

4. Quick Check:

   Correct move directions fix search [OK]

Hint: From bottom-left, move right if smaller, up if bigger [OK]

Common Mistakes:

• Swapping row and column moves
• Wrong initial position for search
• Incorrect loop condition causing infinite loop

5. Given a 2D matrix where each row and column is sorted ascending, write a function to count how many times a target appears in the matrix efficiently. Which approach is best?

hard

A. Start from top-right and move left/down counting matches (O(m+n))

B. Traverse entire matrix counting matches (O(m*n))

C. Use binary search on each row and sum counts (O(m*log n))

D. Flatten matrix to 1D array and use binary search once (O(m*n))

Solution

1. Step 1: Understand time complexities

   Full traversal is slow (O(m*n)), binary search per row is better but still costly.

2. Step 2: Use top-right start to count efficiently

   Moving left/down lets you skip rows or columns, counting matches in O(m+n) time.

3. Final Answer:

   Start from top-right and move left/down counting matches (O(m+n)) -> Option A

4. Quick Check:

   Top-right traversal counts efficiently [OK]

Hint: Top-right start counts matches in linear time [OK]

Common Mistakes:

• Using full traversal wasting time
• Flattening matrix losing sorted structure
• Binary search per row misses column info