Aug 7, 2023
Edit me

#. Problem

Go to the problem on leetcode

1. My approach (binary search x2)

Easy solution.

function searchMatrix(arr: number[][], target: number): boolean {
    
    let [l, r]:[number, number] = [0, arr.length-1];
    let mid = Math.floor((l+r)/2);

    while(l < r){
        if(arr[mid][0] === target){
            break;
        } else if(arr[mid][0] < target){
            l = mid+1;
        } else {
            r = mid-1;
        }

        mid = Math.floor((l+r)/2);
    }

    if(!arr[mid]) return false;
    if(mid > 0 && arr[mid][0] > target) mid--;

    l = 0;
    r = arr[mid].length;
    let colMid = Math.floor((l+r)/2);
    while(l < r){
        if(arr[mid][colMid] === target){
            break;
        } else if(arr[mid][colMid] < target){
            l = colMid+1;
        } else {
            r = colMid-1;
        }

        colMid = Math.floor((l+r)/2);
    }

    console.log(mid, colMid)
    return (arr[mid][colMid] === target);
};

O(log(N+M))

2. Easier Solution

Flatten the 2d array to 1d array and do the search. So straight forward, can’t believe I couldn’t think about this.

function searchMatrix(matrix: number[][], target: number): boolean {
    return (matrix.flatMap(array => array)).find(num => num === target) !== undefined ? true : false
};

Time complexity would be a bit tricky. flatMap(?) * find(logN) Don’t know what flatMap would cost.

3. Epilogue

What I’ve learned from this exercise:

  • Think about simple solution, also using existing libraries.