O(log(mn)) solution considered (m*n) overflow


  • 0
    D

    Hi all,

    I found most of the solutions given here consider the matrix as a sorted array, but that might cause overflow if m, n are large. I have a solution using binary search twice and it's pretty close to binary search in usual way as I compare target to the last element in each row instead of the first element.

    public class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            int m = matrix.length;
            int n = matrix[0].length;
            int iLo = 0;
            int iHi = m-1;
            while(iLo < iHi){
                int iMid = (iLo + iHi)/2;
                if(matrix[iMid][n-1] == target) return true;
                else if(matrix[iMid][n-1] < target) iLo = iMid + 1;
                else iHi = iMid;
            }
            int jLo = 0;
            int jHi = n-1;
            while(jLo < jHi){
                int jMid = (jLo + jHi)/2;
                if(matrix[iLo][jMid] == target) return true;
                else if(matrix[iHi][jMid] < target) jLo = jMid + 1;
                else jHi = jMid - 1;
            }
            return matrix[iLo][jLo] == target;
        }
    }

  • 0
    C

    If m and n are too large, it would be better to compute iMid = iLo + (iHi - iLo)/2 to make sure overflow doesn't occur even at this point!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.