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.