Java binary search O(nlogm + mlogn) runtime


  • 1
    public class Solution {
        public int minArea(char[][] image, int x, int y) {
            int m = image.length;
            int n = image[0].length;
            int start = y;// y is column
            int end = n - 1;
            int mid;
            // find last column containing black pixel
            while (start < end) {
                mid = start + (end - start) / 2 + 1;
                if (checkColumn(image, mid)) {
                    start = mid;
                } else {
                    end = mid - 1;
                }
            }
            int right = start;
            
            start = 0;
            end = y;
            // find first column containing black pixel
            while (start < end) {
                mid = start + (end - start) / 2;
                if (checkColumn(image, mid)) {
                    end = mid;
                } else {
                    start = mid + 1;
                }
            }
            int left = start;
            
            start = x; // x is row
            end = m - 1;
            // find first row containing black pixel
            while (start < end) {
                mid = start + (end - start) / 2 + 1;
                if (checkRow(image, mid)) {
                    start = mid;
                } else {
                    end = mid - 1;
                }
            }
            int down = start;
            
            start = 0;
            end = x;
            // find first row containing black pixel
            while (start < end) {
                mid = start + (end - start) / 2;
                if (checkRow(image, mid)) {
                    end = mid;
                } else {
                    start = mid + 1;
                }
            }
            int up = start;
            
            return (right - left + 1) * (down - up + 1);
        }
        
        private boolean checkColumn(char[][] image, int col) {
            for (int i = 0; i < image.length; i++) {
                if (image[i][col] == '1') {
                    return true;
                }
            }
            return false;
        }
        
        private boolean checkRow(char[][] image, int row) {
            for (int j = 0; j < image[0].length; j++) {
                if (image[row][j] == '1') {
                    return true;
                }
            }
            return false;
        }
    }

  • 0

    It's not O(logm + logn).


  • 0

    is that O(mlogn + nlogm) ?


  • 0
    S
    This post is deleted!

  • 0
    S

    It's Mlog(N1N2)+Nlog(M1M2)

    N1+N2=N = image.length M1+M2=M=image[0].length


Log in to reply
 

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