Description

You are given an m x n integer matrix matrix with the following two properties:

  • Each row is sorted in non-decreasing order.
  • The first integer of each row is greater than the last integer of the previous row. Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Example 1:

1Input: matrix = [
2    [1,3,5,7],
3    [10,11,16,20],
4    [23,30,34,60]
5], target = 3
6Output: true

Example 2:

1Input: matrix = [
2    [1,3,5,7],
3    [10,11,16,20],
4    [23,30,34,60]
5], target = 13
6Output: false

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -10^4 <= matrix[i][j], target <= 10^4

Solution

This problem can be solved using binary search. Here, you can think of this 2D matrix as a 1D array. The idea is to start the binary search from first row last element. If the target is greater than the last element of the row, then we move to the next row. If the target is less than the last element of the row, then we perform binary search on that row.

 1class Solution {
 2    public boolean searchMatrix(int[][] matrix, int target) {
 3        int row = 0;
 4        int col = matrix[0].length - 1;
 5
 6        while (row < matrix.length && col >= 0) {
 7            if (matrix[row][col] == target) {
 8                return true;
 9            } else if (matrix[row][col] < target) {
10                row++;
11            } else {
12                return binarySearch(matrix[row], target);
13            }
14        }
15        return false;
16    }
17
18    private boolean binarySearch(int[] arr, int target) {
19        int start = 0;
20        int end = arr.length - 1;
21
22        while (start <= end) {
23            int mid = start + (end - start) / 2;
24            if (arr[mid] == target) {
25                return true;
26            } else if (arr[mid] < target) {
27                start = mid + 1;
28            } else {
29                end = mid - 1;
30            }
31        }
32        return false;
33    }
34}
  • Time Complexity: O(log(m * n))
  • Space Complexity: O(1)