Search in 2D Matrix in DSA Javascript - 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 column each step.

beginner

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

Because from the top-right, moving left decreases the value and moving down increases the value, helping to decide the direction to move based on comparison with 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

Show the step-by-step search process for target 5 in this matrix: [[1, 4, 7], [2, 5, 8], [3, 6, 9]]

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

beginner

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

The search moves out of the matrix boundaries (row index exceeds or column index becomes negative), and the target is concluded to be absent.

In a sorted 2D matrix, where should you start searching for a target to use the efficient approach?

A Top-right corner

B Bottom-left 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 during the search, what is the next move?

A Move down

B Move right

C Move left

D Move up

Moving left decreases the number, helping to find smaller values closer to the target.

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

A O(m * n)

B O(m + n)

C O(1)

D O(log(m * n))

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, which direction do you move?

A Left

B Down

C Right

D Up

Moving left leads to smaller numbers in the sorted matrix.

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

A Column index < 0 only

B Column index > number of columns

C Row index < 0

D Row index >= number of rows or column index < 0

Search ends when row index goes beyond last row or column index goes before first column.

Explain how to search for a target in a 2D matrix where each row and column is sorted.

Think about how to eliminate rows or columns step by step.

Describe the time complexity and why the top-right corner approach is efficient for searching in a sorted 2D matrix.

Consider how many steps maximum the search can take.