240. Search a 2D Matrix II #

Problem #

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

Problem Summary #

Write an efficient algorithm to search for a target value target in an m x n matrix matrix. This matrix has the following properties:

• The elements in each row are sorted in ascending order from left to right.
• The elements in each column are sorted in ascending order from top to bottom.

Solution Ideas #

• Given a two-dimensional matrix, the characteristic of the matrix is that within each row, elements increase as the index increases, and within each column, elements also increase as the index increases. However, adjacent rows do not have an ordering relationship. For example, the last element of the first row is larger than the first element of the second row. We need to design an algorithm that can efficiently find a number in this matrix; if found, output true, otherwise output false.
• This problem is an enhanced version of Problem 74. The two-dimensional matrix in Problem 74 is completely an ordered one-dimensional matrix, but in this problem, if it is flattened into one dimension, it is not ordered. Since each row or each column is ordered, we can use binary search in each row or each column one by one. This gives a time complexity of O(n log n).
• There is also a simulation solution. Through observation, we find a characteristic of this matrix: the elements in the rightmost column are the largest elements in their respective rows. So we can start from the rightmost column and find the first element that is larger than target; the row where this element is located is the row we will search next. Searching within a row starts from the rightmost side and moves left, with time complexity O(n). Including the initial search in the rightmost column, which has time complexity O(m), the final time complexity is O(m+n).

Code #

package leetcode

// Solution 1: simulation, time complexity O(m+n)
func searchMatrix240(matrix [][]int, target int) bool {
	if len(matrix) == 0 {
		return false
	}
	row, col := 0, len(matrix[0])-1
	for col >= 0 && row <= len(matrix)-1 {
		if target == matrix[row][col] {
			return true
		} else if target > matrix[row][col] {
			row++
		} else {
			col--
		}
	}
	return false
}

// Solution 2: binary search, time complexity O(n log n)
func searchMatrix2401(matrix [][]int, target int) bool {
	if len(matrix) == 0 {
		return false
	}
	for _, row := range matrix {
		low, high := 0, len(matrix[0])-1
		for low <= high {
			mid := low + (high-low)>>1
			if row[mid] > target {
				high = mid - 1
			} else if row[mid] < target {
				low = mid + 1
			} else {
				return true
			}
		}
	}
	return false
}