Question

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

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:

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

Example 2:

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

Constraints:

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

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:

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

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;
        }
    }
}

############

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int left = 0, right = m * n - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            int x = mid / n, y = mid % n;
            if (matrix[x][y] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return matrix[left / n][left % n] == target;
    }
}

// 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:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1
        while left <= right:
            mid = (left + right) >> 1
            x, y = divmod(mid, n) # note: divide column count
            if matrix[x][y] == target:
                return True
            elif matrix[x][y] > target:
                right = mid - 1
            else:
                left = mid + 1
        return False

###########

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1
        while left < right:
            mid = (left + right) >> 1
            x, y = divmod(mid, n)
            if matrix[x][y] >= target:
                right = mid
            else:
                left = mid + 1
        return matrix[left // n][left % n] == target

############

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

func searchMatrix(matrix [][]int, target int) bool {
	m, n := len(matrix), len(matrix[0])
	left, right := 0, m*n-1
	for left < right {
		mid := (left + right) >> 1
		x, y := mid/n, mid%n
		if matrix[x][y] >= target {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return matrix[left/n][left%n] == target
}

function searchMatrix(matrix: number[][], target: number): boolean {
    const m = matrix.length;
    const n = matrix[0].length;
    let left = 0;
    let right = m * n;
    while (left < right) {
        const mid = (left + right) >>> 1;
        const i = Math.floor(mid / n);
        const j = mid % n;
        if (matrix[i][j] === target) {
            return true;
        }

        if (matrix[i][j] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return false;
}

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
    const m = matrix.length,
        n = matrix[0].length;
    let left = 0,
        right = m * n - 1;
    while (left < right) {
        const mid = (left + right + 1) >> 1;
        const x = Math.floor(mid / n);
        const y = mid % n;
        if (matrix[x][y] <= target) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return matrix[Math.floor(left / n)][left % n] == target;
};

use std::cmp::Ordering;
impl Solution {
    pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
        let m = matrix.len();
        let n = matrix[0].len();
        let mut i = 0;
        let mut j = n;
        while i < m && j > 0 {
            match matrix[i][j - 1].cmp(&target) {
                Ordering::Equal => return true,
                Ordering::Less => i += 1,
                Ordering::Greater => j -= 1,
            }
        }
        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;
    }
}

############

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int left = 0, right = m * n - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            int x = mid / n, y = mid % n;
            if (matrix[x][y] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return matrix[left / n][left % n] == target;
    }
}

// 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:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1
        while left <= right: # must be <=, not <, for matrax=[[1]],target=1
            mid = (left + right) >> 1
            x, y = divmod(mid, n) # note: divide column count
            if matrix[x][y] == target:
                return True
            elif matrix[x][y] > target:
                right = mid - 1
            else:
                left = mid + 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

func searchMatrix(matrix [][]int, target int) bool {
	m, n := len(matrix), len(matrix[0])
	left, right := 0, m*n-1
	for left < right {
		mid := (left + right) >> 1
		x, y := mid/n, mid%n
		if matrix[x][y] >= target {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return matrix[left/n][left%n] == target
}

function searchMatrix(matrix: number[][], target: number): boolean {
    const m = matrix.length;
    const n = matrix[0].length;
    let left = 0;
    let right = m * n;
    while (left < right) {
        const mid = (left + right) >>> 1;
        const i = Math.floor(mid / n);
        const j = mid % n;
        if (matrix[i][j] === target) {
            return true;
        }

        if (matrix[i][j] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return false;
}

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
    const m = matrix.length,
        n = matrix[0].length;
    let left = 0,
        right = m * n - 1;
    while (left < right) {
        const mid = (left + right + 1) >> 1;
        const x = Math.floor(mid / n);
        const y = mid % n;
        if (matrix[x][y] <= target) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return matrix[Math.floor(left / n)][left % n] == target;
};

use std::cmp::Ordering;
impl Solution {
    pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
        let m = matrix.len();
        let n = matrix[0].len();
        let mut i = 0;
        let mut j = n;
        while i < m && j > 0 {
            match matrix[i][j - 1].cmp(&target) {
                Ordering::Equal => return true,
                Ordering::Less => i += 1,
                Ordering::Greater => j -= 1,
            }
        }
        false
    }
}

74 - Search a 2D Matrix

Question

Algorithm

Note

Code

Algorithm - binary search

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Note

Code

Algorithm - binary search

All Problems

All Solutions