Question

Formatted question description: https://leetcode.ca/all/74.html

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 from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example,

Example 1:

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


Example 2:

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

@tag-array
@tag-binarysearch

Algorithm

It is also possible to use double pointers, i points to 0, j points to the number of columns, so the first number to be verified is the number in the upper right corner of the two-dimensional array.

  • If this number is equal to target, return true directly;
  • if it is greater than target, it means to decrease For small numbers, the number of columns j will decrease by 1;
  • if it is less than target, it means that the number should be increased, and the number of rows i will increase by 1.
  • If the while loop exits and the target is not found, return false directly

Note

Tried two options:

  1. The diagonal line from the upper left to the lower right is the baseline to find, because this diagonal is the CLP after the matrix is flattened into a sorted list. But no, moving row+1 or col-1 will skip possible targets
  2. Then I tried again. The first column is a binary search first, and then a binary search of the target row. Similarly, some targets may be skipped, when the pointer is +1 or -1

The key is to find a turning point, a certain point, the front is smaller than him, and the back is bigger than him: in this question, it is the point in the upper right corner.

The same is true for the lower left corner.

Code

Java

  • 
    public class Search_a_2D_Matrix {
    
        class Solution_binarySearch {
            public boolean searchMatrix(int[][] matrix, int target) {
                if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                    return false;
                }
    
                int left = 0, right = matrix.length;
                while (left < right) {
                    int mid = (left + right) / 2;
                    if (matrix[mid][0] == target) return true;
                    if (matrix[mid][0] < target) left = mid + 1;
                    else right = mid;
                }
    
                int tmp = (right > 0) ? (right - 1) : right;
                left = 0;
                right = matrix[tmp].length;
                while (left < right) {
                    int mid = (left + right) / 2;
                    if (matrix[tmp][mid] == target) return true;
                    if (matrix[tmp][mid] < target) left = mid + 1;
                    else right = mid;
                }
                return false;
    
            }
        }
    
        public class Solution {
            public boolean searchMatrix(int[][] m, int target) {
    
                if (m == null || m.length == 0)     return false;
                if (m[0].length == 0)   return false;
    
                // start from top right
                int i = 0, j = m[0].length - 1;
    
                while (i < m.length && j >= 0) {
    
                    if (target > m[i][j])   i++;
                    else if (target < m[i][j])  j--;
                    else    return true;
                }
    
                return false;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/search-a-2d-matrix/
    // Time: O(log(MN))
    // Space: O(1)
    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& A, int target) {
            if (A.empty() || A[0].empty()) return false;
            int L = 0, R = A.size() - 1;
            while (L <= R) {
                int M = (L + R) / 2;
                if (A[M][0] == target) return true;
                if (A[M][0] < target) L = M + 1;
                else R = M - 1;
            }
            if (R == -1) return false;
            int row = R;
            L = 0, R = A[0].size() - 1;
            while (L <= R) {
                int M = (L + R) / 2;
                if (A[row][M] == target) return true;
                if (A[row][M] < target) L = M + 1;
                else R = M - 1;
            }
            return false;
        }
    };
    
  • class Solution(object):
      def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if len(matrix) == 0 or len(matrix[0]) == 0:
          return False
    
        m = len(matrix)
        n = len(matrix[0])
    
        start, end = 0, m * n - 1
        while start + 1 < end:
          mid = start + (end - start) / 2
          if matrix[mid / n][mid % n] > target:
            end = mid
          elif matrix[mid / n][mid % n] < target:
            start = mid
          else:
            return True
        if matrix[start / n][start % n] == target:
          return True
        if matrix[end / n][end % n] == target:
          return True
        return False
    
    

Algorithm - binary search

Since the matrix is sorted ascending in each row, and the first integer of each row is greater than the last integer of the previous row, the m x n matrix can be reshaped to a 1D array, where each row is concatenated after the previous row, and binary search can be done on the 1D array.

In practice, the reshape procedure is not necessary and only the idea needs to be used. Initially, set low to be 0 and high to be m x n - 1. The loop condition is low <= high. Each time, select mid to be the average of low and high, find the row and the column according to mid, and check the number. The rest procedure is the same as binary search.

  • class Solution_2d_to_1d {
        public boolean searchMatrix(int[][] matrix, int target) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
                return false;
            int rows = matrix.length;
            int columns = matrix[0].length;
            int low = 0;
            int high = rows * columns - 1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                int num = matrix[mid / columns][mid % columns];
                if (num == target)
                    return true;
                else if (num > target)
                    high = mid - 1;
                else
                    low = mid + 1;
            }
            return false;
        }
    }
    
  • // OJ: https://leetcode.com/problems/search-a-2d-matrix/
    // Time: O(log(MN))
    // Space: O(1)
    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& A, int target) {
            if (A.empty() || A[0].empty()) return false;
            int L = 0, R = A.size() - 1;
            while (L <= R) {
                int M = (L + R) / 2;
                if (A[M][0] == target) return true;
                if (A[M][0] < target) L = M + 1;
                else R = M - 1;
            }
            if (R == -1) return false;
            int row = R;
            L = 0, R = A[0].size() - 1;
            while (L <= R) {
                int M = (L + R) / 2;
                if (A[row][M] == target) return true;
                if (A[row][M] < target) L = M + 1;
                else R = M - 1;
            }
            return false;
        }
    };
    
  • class Solution(object):
      def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if len(matrix) == 0 or len(matrix[0]) == 0:
          return False
    
        m = len(matrix)
        n = len(matrix[0])
    
        start, end = 0, m * n - 1
        while start + 1 < end:
          mid = start + (end - start) / 2
          if matrix[mid / n][mid % n] > target:
            end = mid
          elif matrix[mid / n][mid % n] < target:
            start = mid
          else:
            return True
        if matrix[start / n][start % n] == target:
          return True
        if matrix[end / n][end % n] == target:
          return True
        return False
    
    

All Problems

All Solutions