LeetCode 74. Search a 2D Matrix

🗓️ Daily LeetCoding Challenge August, Day 7

Simple Search

Think from-simple-to-complex! First, I just simply search over the matrix and check if target value is in each line. Fortunately, this code didn’t trigger TLE.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for i in range(len(matrix)):
            if matrix[i][-1] >= target:
                if target in matrix[i]:
                    return True
                else:
                    return False

Binary Search

However in order to improve runtime, it’s better to use binary search than just checking with in. Similar to the previous simple search code.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for arr in matrix:
            if arr[-1] >= target:
                # Binary-Search
                l,h = 0,len(arr)
                while l < h:
                    m = (l+h)//2
                    if arr[m] == target:
                        return True
                    if arr[m] > target:
                        h = m
                    else:
                        l = m+1
        return False

Sorted List

References

While I was searching through solutions, someone point out that this problem can be treated as sorted-list not 2D matrix. It’s because the problem tells us to check ‘whether target is present or not’. Even if the problem tells us to find out the index, we can simply know it from the index in sorted-list. (e.g 3*4 matrix, 10th number == target, then position = (10//4, 10%2) = (2,2))

class Solution {
public:
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        int n = matrix.size();
        int m = matrix[0].size();
        int l = 0, r = m * n - 1;
        while (l != r){
            int mid = (l + r - 1) >> 1;
            if (matrix[mid / m][mid % m] < target)
                l = mid + 1;
            else 
                r = mid;
        }
        return matrix[r / m][r % m] == target;
    }
};