Search in 2D Matrix in DSA Typescript - Deep Dive

Overview - Search in 2D Matrix

What is it?

Searching in a 2D matrix means finding whether a specific number or value exists inside a grid of rows and columns. The matrix is like a table with numbers arranged in rows and columns. We want to quickly check if the number we want is somewhere in this table without looking at every single number.

Why it matters

Without an efficient way to search in a 2D matrix, finding a number would take a long time, especially if the matrix is large. This would slow down programs that rely on quick lookups, like maps, games, or data analysis tools. Efficient searching saves time and makes software faster and more responsive.

Where it fits

Before learning this, you should understand basic arrays and how to access elements in a 2D array. After this, you can learn about more advanced search algorithms, sorting techniques, and data structures like trees or graphs that help with searching in complex data.

Mental Model

Core Idea

Searching in a 2D matrix is like looking for a word in a crossword puzzle by using the order and arrangement of letters to skip unnecessary checks.

Think of it like...

Imagine a library with books arranged on shelves in order. Instead of checking every book, you use the order to jump directly to the shelf and book where your desired title might be, saving time.

Matrix (rows x columns):
┌─────┬─────┬─────┐
│ 1   │ 3   │ 5   │
├─────┼─────┼─────┤
│ 7   │ 9   │ 11  │
├─────┼─────┼─────┤
│ 13  │ 15  │ 17  │
└─────┴─────┴─────┘
Search path example:
Start at top-right -> move left if target smaller -> move down if target larger

Build-Up - 6 Steps

1

Foundation

Understanding 2D Matrix Structure

Concept: Learn what a 2D matrix is and how to access its elements using row and column indexes.

A 2D matrix is like a table with rows and columns. You can think of it as an array of arrays. For example, matrix[0][1] means the element in the first row and second column. Accessing elements is done by specifying the row first, then the column.

Result

You can read or write any element in the matrix by using two indexes: row and column.

Understanding how to access elements in a 2D matrix is the foundation for any operation, including searching.

2

Foundation

Linear Search in 2D Matrix

Concept: Learn the simplest way to search by checking every element one by one.

To find a number, start from the first row and first column, check each element moving across the row, then move to the next row. Repeat until you find the number or reach the end.

Result

If the number exists, you find it after checking some or all elements; otherwise, you conclude it's not there.

Linear search works but is slow for large matrices because it checks every element without using any order.

3

Intermediate

Search in Sorted Rows and Columns

🤔Before reading on: do you think searching row by row is faster if rows and columns are sorted? Commit to yes or no.

Concept: Use the fact that rows and columns are sorted to skip parts of the matrix.

If each row and each column is sorted ascending, start from the top-right corner. Compare the target with the current element: - If target is smaller, move left (because all elements below are bigger). - If target is bigger, move down (because all elements to the left are smaller). Repeat until you find the target or go out of bounds.

Result

You find the target faster by eliminating whole rows or columns at each step.

Knowing the matrix is sorted both ways lets you skip large parts, making search much faster than checking every element.

4

Intermediate

Binary Search on Each Row

🤔Before reading on: do you think binary searching each row separately is faster than linear search? Commit to yes or no.

Concept: Apply binary search on each row individually to find the target faster.

Since each row is sorted, you can use binary search on each row: - For each row, do binary search to find the target. - If found, return true. - If not found in any row, return false. Binary search splits the row in half repeatedly, reducing checks.

Result

Search time improves from checking all elements to checking fewer elements per row.

Using binary search on rows leverages sorting to speed up search, but it still checks multiple rows.

5

Advanced

Binary Search Treating Matrix as 1D Array

🤔Before reading on: can you guess how to treat a 2D matrix as a 1D array for binary search? Commit to your idea.

Concept: Flatten the matrix conceptually and apply binary search on the entire matrix as if it was one sorted list.

If the matrix is sorted row-wise and the first element of each row is greater than the last of the previous row, you can: - Treat the matrix as a single sorted list of size rows x columns. - Use binary search with indexes converted back to row and column: row = Math.floor(index / columns) col = index % columns - Compare target with matrix[row][col] and adjust search range accordingly.

Result

Search is done in O(log(rows x columns)) time, very efficient.

This method uses the matrix's sorted order fully, enabling the fastest search possible in such a matrix.

6

Expert

Handling Edge Cases and Performance Tradeoffs

🤔Before reading on: do you think the top-right corner search always beats binary search on rows? Commit to yes or no.

Concept: Understand when each search method is best and how to handle special cases like empty matrix or duplicates.

Top-right corner search is O(rows + columns), good for large matrices with sorted rows and columns. Binary search on rows is O(rows x log(columns)), better if rows are few. Binary search on entire matrix is O(log(rows x columns)), best if matrix is sorted as a whole. Handle empty matrix by returning false immediately. Duplicates require careful comparison but do not affect correctness. Choose method based on matrix size and sorting properties.

Result

You pick the best search method for your matrix and avoid bugs with edge cases.

Knowing the strengths and limits of each method helps write robust and efficient code in real-world scenarios.

Under the Hood

The search algorithms use the matrix's sorted properties to reduce the number of comparisons. The top-right corner search moves left or down to eliminate rows or columns. Binary search divides the search space in half repeatedly by calculating midpoints and comparing the target. Index calculations map 1D positions back to 2D coordinates.

Why designed this way?

These methods were designed to exploit sorting to avoid checking every element, which is slow. The top-right corner approach is simple and uses the matrix's two-dimensional order. Binary search is a classic fast search for sorted data, adapted here for 2D by flattening or per-row application.

Matrix:
┌─────┬─────┬─────┐
│ 1   │ 3   │ 5   │ ← Start here (top-right)
├─────┼─────┼─────┤
│ 7   │ 9   │ 11  │
├─────┼─────┼─────┤
│ 13  │ 15  │ 17  │
└─────┴─────┴─────┘
Search moves:
-> Compare target with current
↓ If target > current, move down
← If target < current, move left

Binary search on 1D:
Index range: 0 to rows*cols -1
Mid = Math.floor((low + high) / 2)
Row = Math.floor(Mid / cols)
Col = Mid % cols
Compare target with matrix[Row][Col]

Myth Busters - 3 Common Misconceptions

Quick: Does sorting only rows guarantee fast search in the matrix? Commit yes or no.

Common Belief: If each row is sorted, searching is always fast by just scanning rows.

Reality: Sorting rows alone is not enough; columns must also be sorted or the matrix must be sorted as a whole for efficient search methods like top-right corner or binary search on 1D.

Why it matters: Assuming row sorting alone is enough can lead to slow searches or incorrect results when using advanced search methods.

Quick: Is linear search always the best way to find an element in a matrix? Commit yes or no.

Common Belief: Checking every element one by one is simple and good enough for all cases.

Reality: Linear search is slow for large matrices and ignores sorting, making it inefficient compared to methods that use order to skip elements.

Why it matters: Using linear search on large sorted matrices wastes time and resources, slowing down programs.

Quick: Can you always treat any 2D matrix as a 1D sorted array for binary search? Commit yes or no.

Common Belief: Any 2D matrix can be flattened and binary searched as a 1D array.

Reality: Only matrices sorted row-wise with each row's first element greater than the previous row's last element can be treated this way.

Why it matters: Applying 1D binary search on unsorted or partially sorted matrices leads to wrong results.

Expert Zone

1

The top-right corner search exploits the matrix's two-dimensional sorted property, which is a unique pattern not found in one-dimensional arrays.

2

Binary search on the entire matrix requires careful index mapping between 1D and 2D, which can be a source of off-by-one errors if not handled precisely.

3

Handling duplicates in the matrix can complicate search logic, especially for algorithms that rely on strict inequalities.

When NOT to use

Avoid top-right corner search if the matrix is not sorted both row-wise and column-wise. Avoid binary search on 1D if the matrix rows are sorted but not the entire matrix. For unsorted matrices, use linear search or consider sorting first if multiple searches are needed.

Production Patterns

In real systems, top-right corner search is common in grid-based games and spatial data queries. Binary search on 1D is used in databases where data is stored in sorted blocks. Hybrid approaches combine these methods depending on matrix size and query frequency.

Connections

Binary Search

Builds-on

Understanding binary search in 1D arrays is essential to grasp how it extends to searching in 2D matrices by index mapping.

Divide and Conquer Algorithms

Same pattern

Searching in a sorted matrix uses divide and conquer by eliminating large parts of the search space at each step, similar to how quicksort or mergesort work.

Library Book Indexing

Analogy from real world

Just like searching a book in a library by using the catalog and shelf order, searching in a sorted matrix uses order to find elements quickly.

Common Pitfalls

#1 Assuming the matrix is sorted only by rows and applying top-right corner search.

Wrong approach:

function searchMatrix(matrix: number[][], target: number): boolean {
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;
}
// Used on matrix sorted only by rows, not columns

Correct approach:

Use linear search or binary search on each row if columns are not sorted:
function searchMatrix(matrix: number[][], target: number): boolean {
for (const row of matrix) {
if (binarySearch(row, target)) return true;
}
return false;
}

function binarySearch(arr: number[], target: number): boolean {
let low = 0, high = arr.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (arr[mid] === target) return true;
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return false;
}

Root cause:

Misunderstanding the matrix's sorting properties leads to applying the wrong search algorithm.

#2 Trying to binary search the entire matrix as 1D when rows are not sorted relative to each other.

Wrong approach:

function searchMatrix(matrix: number[][], target: number): boolean {
const rows = matrix.length;
const cols = matrix[0].length;
let low = 0, high = rows * cols - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
const r = Math.floor(mid / cols);
const c = mid % cols;
if (matrix[r][c] === target) return true;
else if (matrix[r][c] < target) low = mid + 1;
else high = mid - 1;
}
return false;
}
// Matrix rows not sorted relative to each other

Correct approach:

Use top-right corner search if rows and columns are sorted, or binary search on each row if only rows are sorted.

Root cause:

Incorrect assumption about the matrix's global sorting order.

#3 Not checking for empty matrix before searching.

Wrong approach:

function searchMatrix(matrix: number[][], target: number): boolean {
let row = 0;
let col = matrix[0].length - 1;
// No check if matrix is empty or matrix[0] is undefined
while (row < matrix.length && col >= 0) {
if (matrix[row][col] === target) return true;
else if (matrix[row][col] > target) col--;
else row++;
}
return false;
}

Correct approach:

function searchMatrix(matrix: number[][], target: number): boolean {
if (matrix.length === 0 || matrix[0].length === 0) return false;
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;
}

Root cause:

Overlooking edge cases leads to runtime errors or incorrect results.

Key Takeaways

A 2D matrix is a grid of rows and columns where each element can be accessed by its row and column indexes.

Searching every element one by one works but is slow for large matrices.

If the matrix is sorted by rows and columns, starting from the top-right corner lets you eliminate rows or columns quickly to find the target.

Binary search can be applied on each row or on the entire matrix if it is sorted as a whole, making search very fast.

Choosing the right search method depends on the matrix's sorting properties and size, and handling edge cases is essential for correct results.