[LeetCode] 240. Search a 2D Matrix II

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.

For 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.

Thought process:

Because the rows and columns are sorted, the numbers at the top-right and bottom-left corners are likely to be approximately the median of the matrix. So we borrow the idea of binary search. Let's start at the top-right corner.

Compare the number at the top-right corner with the target. If number < target, we know that target cannot be in this row because number is the largest number in this row. If number > target, we know that target cannot be in this column because number is the smallest number in this column. So in each comparison we can rule out one row or one column.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

public class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0) { return false; } if (matrix[0] == null || matrix[0].length == 0) { return false; } int row = 0, col = matrix[0].length - 1; while (row < matrix.length && col >= 0) { if (matrix[row][col] == target) { return true; } if (matrix[row][col] < target) { row++; } else { col--; } } return false; } }

Time complexity:
Say there're a rows and b columns. The time complexity is O(a + b).