Solve NumberOfDiscIntersections

For the NumberOfDiscIntersections problem of Codility site. it’s a little hard to figure it out.

The Question

At first, I use bruce force method to solve it, the complexity is O(n^^2)

function solution(A) {
    // write your code in JavaScript (Node.js 6.4.0)
    A = A.map((x, i) => [i-x, i+x])
    let c = 0;
    for(i = 0; i< A.length; i++){
        for(j = i+1; j < A.length; j++){
            if(A[i][1] >= A[j][0]){
                c++
                if(c > 10000000) return -1;
            }
        }
    }
    return c;
}

On the web page, they require the worst complexity is O(nlogn), so we need find a better solution.

I searched on web, many people have a solution which sort the boundary of disc, and its complexity is O(nlogn), it suggest to use binary search whose complexity is O(logn), so I try and got this:

function solution(A) {
    // write your code in JavaScript (Node.js 6.4.0)
    A = A.map((x, i) => [i-x, i+x])
    A = A.sort((a,b) => a[0] - b[0])
    let lefts = A.map((x)=>x[0]);
    
    let search = function(list, x){
        let beg = 0;
        let end = list.length -1;
        let result = -1;
        while(beg <= end){
            let mid = Math.floor((beg+end)/2)
            if(list[mid] <= x){
                beg = mid + 1;
                result = mid;
            }else{
                end = mid -1;
            }
        }
        return result;
    }
    
    let c = 0;
    for(i = 0; i< A.length; i++){
        let rank = search(lefts, A[i][1])
        c += (rank+1) - i - 1;
        if(c > 10000000) return -1;
    }
    return c;
}

We first sort the left boundarys, and and then in a loop to find each right boundary’s position in it(using binary search), as the loop is O(n), and binary search is O(logn), so the total complexity is O(nlogn)

But do we still have a better solution?

We can consider the discs as events. for each disc, so each disc has 2 events: open event, and close event. And then we can use stack to trace the events. when a disc open, we push a record, when another disc open, we check how many records are there in the stack, that means the intersection, and when a disc close, we pop the stack.

function solution(A) {
    // write your code in JavaScript (Node.js 6.4.0)
    var events = []
    A.forEach(function(x, i){
        events.push({type: 'left', value: i-x})
        events.push({type: 'right', value: i+x})
    })
    events = events.sort(function(a,b){
        if(a.value != b.value) return a.value - b.value;
        else return (a.type == 'right' ? 1 : -1);
    })

    var c= 0;
    var stack = [];
    for(i = 0; i < events.length; i++){
        let event = events[i];
        
        if(event.type == 'left'){
            c += stack.length;
            if(c > 10000000) return -1;
            stack.push(1);
        }else{
            stack.pop()
        }
    }

    return c;
}

Now the complexity is O(n) now.