Search in 2D Matrix in DSA Go - 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 or bottom-left corner and move either left or down based on comparison with the target, reducing search space step-by-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 values and moving down increases values, allowing easy elimination of rows or columns.

intermediate

In a 2D matrix sorted by rows and columns, what is the time complexity of the search algorithm starting from the top-right corner?

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

What happens if the target is smaller than the current element when searching from the top-right corner?

Move left to the previous column because smaller values are to the left in the same row.

beginner

What happens if the target is larger than the current element when searching from the top-right corner?

Move down to the next row because larger values are below in the same column.

Where should you start searching in a 2D matrix sorted by rows and columns to efficiently find a target?

A Bottom-left corner

B Top-left corner

C Bottom-right corner

D Top-right corner

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

If the current element is greater than the target, what is the next move in the search?

A Move left

B Move down

C Move right

D Move up

Move left to find smaller elements because the matrix is sorted.

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(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 larger than the current element, where do you move next?

A Left

B Right

C Down

D Up

Move down to find larger elements in the same column.

What condition must the 2D matrix satisfy for the top-right corner search method to work correctly?

A Each row is sorted ascending, each column is sorted ascending

B Each row is sorted descending, each column is sorted ascending

C Each row is sorted ascending, each column is sorted descending

D No sorting required

The matrix must be sorted ascending in both rows and columns for the method to work.

Explain step-by-step how to search for a target in a 2D matrix sorted by rows and columns using the top-right corner method.

Think about how the sorted order helps decide the direction to move.

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

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