[leetcode] Search a 2D Matrix II

problem

code

1st try

class Solution {
    // binary search cuz its sorted array
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix[0][0] > target) return false;
        
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] <= target) {
                if(binarySearch(matrix[i], target))
                    return true;
            } else {
                break;
            }
            
        }
        return false;
    }

    
    public boolean binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = (right + left) / 2;
            if (arr[mid] > target) right = mid - 1;
            else if (arr[mid] < target) left = mid + 1;
            else return true;
        }
        return false;
    }
}

Time: O(mlogn); m: matrix.length, n: matrix[0].length
Space: O(1)

binary search => O(logn)

2nd try - leetcode

const solution = (matrix = [[]], target = 0) => {
  let i = 0; // row
  let j = matrix[0].length - 1; // column 
  
  while (i < matrix.length && j >= 0) {
  	if (matrix[i][j] == target) return true;
    else if (matrix[i][j] < target) i++;
    else j--;
  }
  return false;
}

Time: O(n + m)
Space: O(1)

• if target is larger than matrix[i][j], then next row(i) + 1
  - no element matches the target in a column
• if target is smaller than matrix[i][j], then column(j) - 1
  - at column j, there is no element matching the target