Why isn't my program with complexity O(nlogn) not getting accepted?


  • 0
    C

    I have been looking at a couple solutions provided here and not all have the complexity of O(n). Some people have posted solutions with O(nlogn). First of all, are their solutions accepted? If yes, why isn't my solution not completing within the given time?

    Provided below is my solution in JavaScript. The basic idea is to compute the area of the overarching rectangle and match it with the sum of individual rectangles. After that, check for rectangle intersection. If there is no intersection and the areas are equal, then we have a cover.

    Also, I would appreciate any feedback on language choice, tips on improving the general code readability, and debugging the performance of my algorithms in the context of leetcode.

    function rect_intersect(ra, rb) {
        return rb[0] < ra[2] && rb[2] > ra[0]
            && rb[1] < ra[3] && rb[3] > ra[1];
    }
    
    function addNode(root, ridx, val) {
        if (root.val < val) {
            if (root.right === null) {
                root.right = { ridx: [ridx], val, left: null, right: null };
            }
            else {
                addNode(root.right, ridx, val);            
            }
        }
        else if (root.val > val) {
            if (root.left === null) {
                root.left = { ridx: [ridx], val, left: null, right: null };
            }
            else {
                addNode(root.left, ridx, val);
            }
        }
        else if (root.val === val) {
            root.ridx.push(ridx);
        }
    }
    
    function checkIntersection(root, rectangles, rb) {
        if (root && root.val < rb[2]) {
            for (let i = 0; i < root.ridx.length; i++) {
                if (rect_intersect(rectangles[root.ridx[i]], rb)) {
                    return true;
                }
            }
        }
        else {
            return false;
        }
        
        return checkIntersection(root.left, rectangles, rb) ||
            checkIntersection(root.right, rectangles, rb);
    }
    
    /**
     * @param {number[][]} rectangles
     * @return {boolean}
     */
    var isRectangleCover = function(rectangles) {
        let areas = rectangles.map(rect => {
           let a = rect[2] - rect[0];
           let b = rect[3] - rect[1];
           
           return a * b;
        });
        
        let sum_area = areas.reduce((total, area) => total + area, 0);
        
        let lx = _.min(rectangles.map(rect => rect[0]));
        let ly = _.min(rectangles.map(rect => rect[1]));
        let mx = _.max(rectangles.map(rect => rect[2]));
        let my = _.max(rectangles.map(rect => rect[3]));
        let total_area = (mx - lx) * (my - ly);
        
        let isIntersection = false;
        let minXBinTree = { ridx: [0], val: rectangles[0][0], left: null, right: null };
        
        for (let i = 1; i < rectangles.length; i++) {
            if (checkIntersection(minXBinTree, rectangles, rectangles[i])) {
                isIntersection = true;
                break;
            }
            else {
                addNode(minXBinTree, i, rectangles[i][0]);
            }
        }
        
        return !isIntersection && total_area === sum_area;
    };
    

Log in to reply
 

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