Search a 2D Matrix

Medium

The problem

You get a grid of numbers (a list of rows). Each row is sorted from smallest to biggest, and the first number of each row is bigger than the last number of the row above. Return true if target is somewhere in the grid, otherwise false.

Example 1
Input: matrix = [[1, 3, 5], [7, 9, 11], [13, 15, 17]], target = 9
Output: true
9 is in the second row.
Example 2
Input: matrix = [[1, 3, 5], [7, 9, 11], [13, 15, 17]], target = 10
Output: false
10 is not in the grid.

Limits

1 ≤ number of rows, number of columns ≤ 1,000
Rows are sorted, and each row starts after the previous row ends
-1,000,000 ≤ matrix[i][j], target ≤ 1,000,000

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Rows are sorted and each row starts after the previous ends. Is it really a 2D structure?

The idea

Treat the matrix as one sorted array of length rows×cols; mid maps to row = mid / cols, col = mid % cols.

Target: O(log(m·n)) time

Go function shape

func searchMatrix(matrix [][]int, target int) bool

Reference solution

Tested with go test. Try it yourself first, then compare.

// SearchMatrix: rows are sorted and each row starts after the previous one ends, so the matrix is one sorted
// array in disguise. Index mid maps to row mid/cols and column mid%cols.
func SearchMatrix(matrix [][]int, target int) bool {
	rows, cols := len(matrix), len(matrix[0])
	lo, hi := 0, rows*cols-1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		v := matrix[mid/cols][mid%cols]
		switch {
		case v == target:
			return true
		case v < target:
			lo = mid + 1
		default:
			hi = mid - 1
		}
	}
	return false
}

Read the lesson: Binary Search