Search in 2D Matrix in DSA Go

Mental Model

We look for a number in a grid where each row and column is sorted. We start from the top-right corner and move left or down to find the target.

Analogy: Imagine you are in a library with shelves sorted by book height from left to right and top to bottom. You start at the top-right book and move left if the book is too tall or down if it's too short until you find the right book.

Matrix:
1  4  7  11
2  5  8  12
3  6  9  16
10 13 14 17

Start at ↑ top-right corner (11)
Positions:
[0,0] -> 1 -> 4 -> 7 -> [0,3] ↑11
↓
[3,0] 10 -> 13 -> 14 -> 17

Dry Run Walkthrough

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

Goal: Find if 5 exists in the matrix

Step 1: Start at top-right element (11)

Position: [0,3] -> value=11

Why: We start here because it helps decide to move left or down

Step 2: Compare 11 with target 5, 11 > 5, move left

Position: [0,2] -> value=7

Why: Since 11 is bigger than 5, moving left goes to smaller numbers

Step 3: Compare 7 with 5, 7 > 5, move left

Position: [0,1] -> value=4

Why: 7 is bigger than 5, so move left again to smaller numbers

Step 4: Compare 4 with 5, 4 < 5, move down

Position: [1,1] -> value=5

Why: 4 is smaller than 5, so move down to bigger numbers

Step 5: Compare 5 with 5, found target

Position: [1,1] -> value=5

Why: We found the target number in the matrix

Result:

Found 5 at position [1,1]

Annotated Code

DSA Go

package main

import "fmt"

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }
    rows := len(matrix)
    cols := len(matrix[0])
    r, c := 0, cols-1
    for r < rows && c >= 0 {
        if matrix[r][c] == target {
            return true
        } else if matrix[r][c] > target {
            c-- // move left to smaller numbers
        } else {
            r++ // move down to bigger numbers
        }
    }
    return false
}

func main() {
    matrix := [][]int{
        {1, 4, 7, 11},
        {2, 5, 8, 12},
        {3, 6, 9, 16},
        {10, 13, 14, 17},
    }
    target := 5
    found := searchMatrix(matrix, target)
    if found {
        fmt.Println("Found", target)
    } else {
        fmt.Println("Not Found", target)
    }
}

r, c := 0, cols-1

Start at top-right corner of the matrix

for r < rows && c >= 0 {

Loop while inside matrix bounds

if matrix[r][c] == target {

Check if current element is target

c-- // move left to smaller numbers

If current element is bigger than target, move left

r++ // move down to bigger numbers

If current element is smaller than target, move down

Output

Found 5

Complexity Analysis

Time: O(m + n) because we move at most m times down and n times left in the matrix

Space: O(1) because we use only a few variables, no extra space proportional to input

vs Alternative: Compared to searching each element (O(m*n)), this approach is much faster by skipping rows or columns

Edge Cases

Empty matrix

Returns false immediately

DSA Go

if len(matrix) == 0 || len(matrix[0]) == 0 { return false }

Target smaller than smallest element

Returns false after checking top-right element and moving left out of bounds

DSA Go

for r < rows && c >= 0 { ... }

Target larger than largest element

Returns false after moving down out of bounds

DSA Go

for r < rows && c >= 0 { ... }

When to Use This Pattern

When you see a sorted 2D matrix and need to find a number quickly, use the top-right corner search pattern to eliminate rows or columns efficiently.

Common Mistakes

Mistake: Starting search from top-left or bottom-left corner without adjusting moves
Fix: Always start from top-right corner to decide moving left or down correctly

Summary

Searches a target number in a sorted 2D matrix by moving left or down from the top-right corner.

Use when matrix rows and columns are sorted and you want efficient search.

The key insight is starting at the top-right corner lets you eliminate a row or column each step.

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