Search in a 2D Array

1. Problem Description

In a two-dimensional array (where every row has the same length), each row is sorted in increasing order from left to right, and each column is sorted in increasing order from top to bottom. Implement a function that takes such a 2D array and an integer and determines whether the array contains that integer.

2. Approach

• Brute force: traverse every element and check whether it equals the target
• Search from the top right toward the bottom left
  • 

3. Implementation

3.1. Brute Force

// Brute-force solution
// Time: O(mn)
// Space: O(1)
func Find(target int, array [][]int) bool {
	for _, row := range array {
		for _, col := range row {
			if col == target {
				return true
			}
		}
	}

	return false
}

3.2. Search from Top Right to Bottom Left

// Search from the top right toward the bottom left
// 1,2,8,9
// 2,4,9,12
// 4,7,10,13
// 6,8,11,15
// Time: O(m+n)
// Space: O(1)
func Find2(target int, array [][]int) bool {
	if len(array) == 0 || len(array[0]) == 0 {
		return false
	}

	rowBound := len(array) - 1
	colBound := len(array[0]) - 1

	row := 0
	col := colBound
	for row <= rowBound && col >= 0 {
		if array[row][col] == target {
			return true
		} else if array[row][col] < target {
			row++
		} else {
			col--
		}

	}

	return false
}

4. References

• Search in a 2D Array - NowCoder
• LCR 121. Find Target in a 2D Array - LeetCode