Search in 2D Matrix in DSA Go - Deep Dive

Overview - Search in 2D Matrix

What is it?

Searching in a 2D matrix means finding whether a specific number exists inside a grid of numbers arranged in rows and columns. The matrix is usually sorted in some way to help find the number faster. Instead of checking every number one by one, we use smart methods to jump closer to the target quickly. This makes searching much faster and efficient.

Why it matters

Without efficient search methods in 2D matrices, programs would waste a lot of time checking every number, especially when the matrix is large. This would slow down apps like maps, games, or databases that rely on quick lookups. Efficient searching saves time and computing power, making software faster and more responsive.

Where it fits

Before learning this, you should understand basic arrays and how to search in one-dimensional arrays. After this, you can learn more complex search algorithms like binary search trees or graph searches that handle more complicated data.

Mental Model

Core Idea

Searching in a 2D matrix uses the order of rows and columns to quickly eliminate large parts of the matrix and zoom in on the target number.

Think of it like...

Imagine looking for a book in a library where books are arranged by author and then by title. You first pick the right shelf by author (row), then scan the titles (columns) on that shelf. You don't check every book in the library, just the right shelf and section.

Matrix (sorted rows and columns):
┌─────┬─────┬─────┬─────┐
│ 1   │ 4   │ 7   │ 11  │
├─────┼─────┼─────┼─────┤
│ 2   │ 5   │ 8   │ 12  │
├─────┼─────┼─────┼─────┤
│ 3   │ 6   │ 9   │ 16  │
├─────┼─────┼─────┼─────┤
│ 10  │ 13  │ 14  │ 17  │
└─────┴─────┴─────┴─────┘
Start at top-right corner and move left/down to find target.

Build-Up - 6 Steps

1

Foundation

Understanding 2D Matrix Structure

Concept: Learn what a 2D matrix is and how data is stored in rows and columns.

A 2D matrix is like a table with rows and columns. Each position is identified by two numbers: row and column. For example, matrix[1][2] means second row, third column. You can think of it as a grid where you can find values by their position.

Result

You can access any element in the matrix by specifying its row and column.

Knowing how to locate elements in a 2D matrix is the base for searching and manipulating data inside it.

2

Foundation

Linear Search in 2D Matrix

Concept: Searching every element one by one to find the target.

Start from the first row and first column, check each element moving left to right, top to bottom. If the element matches the target, stop and return true. If you reach the end without finding it, return false.

Result

The search checks all elements until it finds the target or finishes the matrix.

Linear search works but is slow for big matrices because it checks every element.

3

Intermediate

Binary Search in Sorted Rows

🤔Before reading on: do you think binary search can be applied directly to the entire 2D matrix or only to individual rows? Commit to your answer.

Concept: Use binary search on each sorted row to find the target faster than linear search.

Since each row is sorted, you can apply binary search on each row separately. For each row, check the middle element. If it matches, return true. If the target is smaller, search left half; if larger, search right half. Repeat for all rows until found or all rows checked.

Result

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

Applying binary search on rows reduces search time but still requires checking multiple rows.

4

Intermediate

Search from Top-Right Corner

🤔Before reading on: do you think starting search from the top-right corner is better or worse than starting from the top-left? Commit to your answer.

Concept: Start at the top-right element and move left or down to find the target efficiently.

Because rows and columns are sorted, start at the top-right element. If this element equals the target, return true. If target is smaller, move left (because left elements are smaller). If target is larger, move down (because lower elements are larger). Repeat until found or out of bounds.

Result

This method finds the target in O(m+n) time, where m is rows and n is columns.

Starting at the top-right corner uses the matrix's sorted property to eliminate rows or columns each step.

5

Advanced

Binary Search Treating Matrix as 1D Array

🤔Before reading on: do you think it's possible to do binary search on the entire matrix as if it was a flat list? Commit to your answer.

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

If the matrix is sorted such that each row's first element is greater than the last element of the previous row, you can treat the matrix as a sorted 1D array. Use binary search with indices mapped back to row and column using division and modulo. Check middle element, adjust search range accordingly.

Result

Search time is O(log(m*n)) which is very efficient for large matrices.

Viewing the matrix as a flat sorted list unlocks the power of binary search on the whole matrix.

6

Expert

Handling Edge Cases and Performance Tradeoffs

🤔Before reading on: do you think the top-right corner search always outperforms binary search on rows? Commit to your answer.

Concept: Understand when each search method is best and how to handle matrices that don't fully meet sorting assumptions.

Top-right corner search is simple and works well when rows and columns are sorted independently. Binary search on rows or flattening requires stricter sorting. For matrices with duplicates or partial sorting, top-right search is safer. Also consider matrix size: for very large matrices, binary search is faster but more complex to implement.

Result

Choosing the right search method depends on matrix properties and performance needs.

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

Under the Hood

The top-right corner search works by comparing the target with the current element. If the target is smaller, it moves left because elements decrease leftwards. If larger, it moves down because elements increase downwards. This eliminates one row or column each step, reducing search space quickly. Binary search uses divide-and-conquer by halving the search space repeatedly, relying on sorted order to decide which half to keep.

Why designed this way?

These methods exploit the matrix's sorted properties to avoid checking every element. The top-right corner approach was designed because it allows a simple decision at each step to move left or down, eliminating large parts of the matrix. Binary search was adapted to 2D matrices to leverage the speed of halving search space, a proven efficient method in 1D arrays.

Start at top-right:
┌─────┬─────┬─────┬─────┐
│     │     │     │  *  │
├─────┼─────┼─────┼─────┤
│     │     │     │     │
├─────┼─────┼─────┼─────┤
│     │     │     │     │
├─────┼─────┼─────┼─────┤
│     │     │     │     │
└─────┴─────┴─────┴─────┘
Move left if target < *, down if target > *.

Myth Busters - 3 Common Misconceptions

Quick: Does starting search from the top-left corner work as efficiently as top-right? Commit yes or no.

Common Belief: Starting from the top-left corner is just as good as starting from the top-right corner for searching.

Reality: Starting from the top-left corner does not allow clear decisions to move only left or down because both directions can have larger or smaller values, making search inefficient.

Why it matters: Using top-left start can cause unnecessary checks and slow down the search, especially in large matrices.

Quick: Can binary search be applied directly on any 2D matrix? Commit yes or no.

Common Belief: Binary search can be applied directly on any 2D matrix regardless of sorting.

Reality: Binary search requires the matrix to be sorted in a specific way (e.g., each row sorted and first element of each row greater than last of previous) to work correctly.

Why it matters: Applying binary search on unsorted or partially sorted matrices leads to incorrect results or missed targets.

Quick: Is linear search always the best fallback method? Commit yes or no.

Common Belief: Linear search is always the safest and best fallback if other methods fail.

Reality: Linear search is safe but very slow for large matrices; sometimes modifying the matrix or using indexing structures is better.

Why it matters: Relying on linear search can cause performance bottlenecks in real applications.

Expert Zone

1

The top-right corner search exploits the matrix's sorted property in two dimensions simultaneously, which is rare in data structures.

2

Binary search on the flattened matrix requires careful index mapping to avoid off-by-one errors and maintain correctness.

3

Handling duplicates in the matrix can complicate search logic, especially for binary search approaches.

When NOT to use

Avoid binary search on matrices that are not fully sorted row-wise and column-wise or where rows are not strictly increasing. Use top-right corner search or linear search instead. For very large datasets, consider building specialized indexes or using database queries.

Production Patterns

In real systems, top-right corner search is often used for quick lookups in sorted grids like game maps or UI grids. Binary search on flattened matrices is used in database indexing and memory-efficient search algorithms. Hybrid approaches combine these with caching or parallel search for speed.

Connections

Binary Search

Builds-on

Understanding binary search in 1D arrays is essential to grasp how it extends to 2D matrices by treating them as sorted lists.

Divide and Conquer Algorithms

Same pattern

Searching in a 2D matrix using binary search applies the divide and conquer principle by halving the search space repeatedly.

Geographical Navigation

Analogy in real life

Navigating a sorted matrix is like navigating a city grid where you decide to go left or down based on your destination, showing how spatial reasoning applies to algorithm design.

Common Pitfalls

#1 Starting search from top-left corner assuming it works like top-right.

Wrong approach:

func searchMatrix(matrix [][]int, target int) bool {
row, col := 0, 0
for row < len(matrix) && col < len(matrix[0]) {
if matrix[row][col] == target {
return true
} else if matrix[row][col] < target {
col++
} else {
row++
}
}
return false
}

Correct approach:

func searchMatrix(matrix [][]int, target int) bool {
row, col := 0, len(matrix[0]) - 1
for row < len(matrix) && col >= 0 {
if matrix[row][col] == target {
return true
} else if matrix[row][col] > target {
col--
} else {
row++
}
}
return false
}

Root cause:

Misunderstanding how the matrix's sorted property allows elimination of rows or columns only from the top-right corner.

#2 Applying binary search on unsorted matrix rows.

Wrong approach:

for _, row := range matrix {
if binarySearch(row, target) {
return true
}
}
return false

Correct approach:

Ensure each row is sorted and the first element of each row is greater than the last of previous row before applying binary search on the whole matrix as a flat array.

Root cause:

Assuming binary search works on any matrix without verifying sorting conditions.

#3 Using linear search for large matrices without optimization.

Wrong approach:

for i := 0; i < len(matrix); i++ {
for j := 0; j < len(matrix[0]); j++ {
if matrix[i][j] == target {
return true
}
}
}
return false

Correct approach:

Use top-right corner search or binary search methods to reduce time complexity.

Root cause:

Not leveraging the matrix's sorted properties to optimize search.

Key Takeaways

A 2D matrix search uses the matrix's sorted rows and columns to find targets efficiently.

Starting from the top-right corner allows quick elimination of rows or columns each step.

Binary search can be applied on rows or the whole matrix if sorting conditions are met.

Choosing the right search method depends on matrix properties and performance needs.

Understanding these methods prevents common mistakes and improves real-world program speed.

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. Use a hash map to store all elements for quick lookup

B. Search each row linearly until the target is found

C. Treat the 2D matrix as a sorted 1D array and use binary search

D. Start from bottom-left corner and move diagonally

Solution

1. Step 1: Understand matrix properties

   The matrix rows are sorted and each row's first element 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 single sorted array, binary search can be used to efficiently find the target.

3. Final Answer:

   Treat the 2D matrix as a sorted 1D array and use binary search -> Option C

4. Quick Check:

   Sorted matrix + binary search = Treat the 2D matrix as a sorted 1D array and use 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 works only for different matrix types

2. Which of the following Go code snippets correctly initializes a 2D matrix of integers with 3 rows and 4 columns?

easy

A. matrix := [3][4]int{}

B. matrix := [][]int{{3,4},{1,2,3},{4,5,6,7}}

C. matrix := make([]int, 3*4)

D. matrix := make([][]int, 3); for i := range matrix { matrix[i] = make([]int, 4) }

Solution

1. Step 1: Understand Go 2D slice initialization

   In Go, a 2D slice is a slice of slices. We first create the outer slice with length 3, then initialize each inner slice with length 4.

2. Step 2: Check each option

   matrix := make([][]int, 3); for i := range matrix { matrix[i] = make([]int, 4) } correctly creates a 3x4 2D slice. matrix := [][]int{{3,4},{1,2,3},{4,5,6,7}} is irregular and not fixed size. matrix := make([]int, 3*4) creates a 1D slice. matrix := [3][4]int{} creates a fixed array, not a slice.

3. Final Answer:

   matrix := make([][]int, 3); for i := range matrix { matrix[i] = make([]int, 4) } -> Option D

4. Quick Check:

   2D slice init with make + loop = matrix := make([][]int, 3); for i := range matrix { matrix[i] = make([]int, 4) } [OK]

Hint: Use make for outer slice, then loop to make inner slices [OK]

Common Mistakes:

• Using make only once creates 1D slice
• Confusing arrays and slices
• Initializing inner slices incorrectly

3. What will be the output of the following Go code that searches for target 5 in the given matrix?

matrix := [][]int{
  {1, 3, 5, 7},
  {10, 11, 16, 20},
  {23, 30, 34, 50},
}
target := 5
found := false
rows := len(matrix)
cols := len(matrix[0])
left, right := 0, rows*cols-1
for left <= right {
  mid := (left + right) / 2
  val := matrix[mid/cols][mid%cols]
  if val == target {
    found = true
    break
  } else if val < target {
    left = mid + 1
  } else {
    right = mid - 1
  }
}
fmt.Println(found)

medium

A. true

B. false

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Understand binary search on 2D matrix

   The code treats the matrix as a 1D sorted array and uses binary search with index mapping mid/cols and mid%cols to access elements.

2. Step 2: Trace the search for target 5

   Target 5 is at matrix[0][2]. The binary search will find it and set found to true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Binary search finds 5 = true [OK]

Hint: Map 1D index to 2D with row=mid/cols, col=mid%cols [OK]

Common Mistakes:

• Incorrect index mapping causing wrong element access
• Off-by-one errors in binary search boundaries
• Not breaking loop when found

4. The following Go code attempts to search for a target in a 2D matrix but has a bug. What is the bug?

func searchMatrix(matrix [][]int, target int) bool {
  rows := len(matrix)
  cols := len(matrix[0])
  left, right := 0, rows*cols
  for left <= right {
    mid := (left + right) / 2
    val := matrix[mid/cols][mid%cols]
    if val == target {
      return true
    } else if val < target {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return false
}

medium

A. right should be initialized to rows*cols - 1

B. mid calculation causes integer overflow

C. matrix indexing should be matrix[mid%rows][mid/cols]

D. Loop condition should be left < right

Solution

1. Step 1: Check initialization of right pointer

   Since indices go from 0 to rows*cols - 1, right should be rows*cols - 1, not rows*cols.

2. Step 2: Understand impact of wrong right value

   Setting right to rows*cols causes out-of-bounds access when mid equals rows*cols, leading to runtime error.

3. Final Answer:

   right should be initialized to rows*cols - 1 -> Option A

4. Quick Check:

   Right boundary off by one causes error = right should be initialized to rows*cols - 1 [OK]

Hint: Right index = total elements - 1, not total elements [OK]

Common Mistakes:

• Using rows*cols instead of rows*cols - 1 for right
• Swapping row and column indices
• Incorrect loop condition causing infinite loop

5. Given a 2D matrix where each row is sorted in ascending order but the first integer of each row may be smaller than the last integer of the previous row, which approach is best to search for a target value efficiently?

hard

A. Perform binary search on each row separately

B. Start from top-right corner and move left/down based on comparison

C. Use binary search treating the matrix as a sorted 1D array

D. Flatten the matrix into a 1D slice and sort it before searching

Solution

1. Step 1: Analyze matrix properties

   Since rows are sorted but rows are not strictly increasing overall, the matrix is not globally sorted.

2. Step 2: Choose search strategy

   Binary search on entire matrix won't work. Binary search on each row is O(m log n). Starting from top-right corner and moving left/down is O(m+n) and efficient.

3. Final Answer:

   Start from top-right corner and move left/down based on comparison -> Option B

4. Quick Check:

   Partial row sorting + top-right search = Start from top-right corner and move left/down based on comparison [OK]

Hint: Top-right corner search works when rows sorted but matrix not fully sorted [OK]

Common Mistakes:

• Assuming full matrix is sorted for binary search
• Flattening and sorting wastes time
• Ignoring matrix properties leads to wrong approach