Number Of Disc Intersections – Codility 100% Correct Javascript Solution

The Number of Disc Intersections is the hardest challenge so far, at least for me. I had to go seriously out of the box for this one, but in the end it proved to be a very fun solution.

Description of the algorithm

It may be a bit hard to understand so I commented the code a lot. The trick here is to create two arrays containing the left boundaries of all circles (opening positions) in the first array, and the right boundaries (the closing positions) in the other one.

The second step is to sort these two ascending.

The idea here is that we will count the number of open circles to the left of each closing boundary.

To do that, once we have them sorted ascending, we iterate over both of them with two counters: i over the right array and j over the left array. We use a for loop for the right array and an inner while loop to iterate over the left array under the conditions that :

• we haven’t iterated in the left array above the last position of the array
• the current right boundary is larger or equal then the current left boundary.

The second condition assures that we are counting all the open circles that are open before the current circle closes (which is represented by the right boundary).
At each inner loop we add the number of intersecting discs to the left of the boundary. The intersecting discs are the number of open discs, minus the number of closed discs at a certain point, which is j-i.

Let’s take the example in the probleme of an array A containing at each position a disc of radius represented by the value of the element at that position.

Initially we have:

A[0] = 1
A[1] = 5
A[2] = 2
A[3] = 1
A[4] = 4
A[5] = 0

Which means that the sorted left and right arrays will look like this:

Left Right
-4 1
-1 4
0 4
0 5
2 6
5 8

Ok so now the fun part starts.
We iterate through the right array with a for loop, and at each element we count how many open circles are containing the current element (thus intersecting with it).
Right Iteration – element 0: 4 discs are open to the left of the disc. We iterate over each of them on the left array, and at each step we add j-i to the sum. It’s j-i because each time we increase the i, we close one circle.
The result sum is 0-(0) + 1-0 + 2-0 + 3-0 = 6; We now move on because the next left element (2) is larger than the current right element (1). i becomes 1, j is 4.

Right Iteration – element 1
The sum is augmented with 4 -1= 3 so the sum becomes 9.
We pass on to the next element (because 4 < 5). i becomes 2, j is 5.

Right Iteration – element 2
The right element is still smaller than the left one so nothing happens at this step. i becomes 3, j is the same, 5.

Right Iteration – element 3
We add j-i = 5 -3 = 2 so the sum becomes 11.
From now on the inner loop does not start because j becomes equal with 6, which is the length of A.
The next iterations over the right side do no longer affect the result.

Solution

Here is the javascript solution with comments in case you got lost.

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

   function sortAsc(a, b) {
    return (a - b)
   }
   
   function solution(A) {
     let counter = 0
     let j= 0;
     let leftLimit = [];
     let rightLimit = []
   
     //fill the left and right limits of each circle
     for(var i=0; i < A.length; i++) {
      leftLimit[i] =i-A[i];
      rightLimit[i] =i+A[i];
     } 

     //sort them in an ascending order - why ? Basically we will rearrange their limits in an ascending way, we will have in leftLimit all open circles while  in the right we will have where the next circle closes
     leftLimit.sort(sortAsc)
     rightLimit.sort(sortAsc)

     //loop through all the elements of the RIGHT boundaries
     for(var i= 0; i<A.length; i++) {
      //this is the tricky part to understand
      //on the left we have the boundaries of open circles, on the right the boundary of the next circle
      //as long as there are circles open (rightLimit[i] >= leftLimit[j]) and (j < A.length)
      while(j < A.length && rightLimit[i] >= leftLimit[j]){
       //we have circles at each position, so, as long as the left boundaries are smaller or equal to the right boundary, there are circles intersecting there 
       //if j surpasses j, it means we overcalculated and we start to decrease the number of intersections   
       counter += j-i;
       //pass to the next open circle
       j++; 
      } 
        if(counter > 10000000) return -1;
     } 
   
     return counter;
   }

Ok, that was not simple but we managed to solve it with an O(N*log(N)) or O(N) complexity.

Here is the report of the algorithm! Let me know if you have a more efficient solution!