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.<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
The second step is to sort these two ascending.<\/p>\n\n\n\n
The idea here is that we will count the number of open circles to the left of each closing boundary. <\/p>\n\n\n\n
To do that, once we have them sorted ascending, we iterate over both of them with two counters: i <\/em>over the right array and j<\/em> 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 :<\/p>\n\n\n\n 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). 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.<\/p>\n\n\n\n Initially we have:<\/p>\n\n\n\n A[0] = 1 Which means that the sorted left and right arrays will look like this:<\/p>\n\n\n\n Left Right Ok so now the fun part starts. Right Iteration – element 1<\/strong> Right Iteration – element 2<\/strong> Right Iteration – element <\/strong>3 Here is the javascript solution with comments in case you got lost.<\/p>\n\n\n\n
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. <\/p>\n\n\n\n
A[1] = 5
A[2] = 2
A[3] = 1
A[4] = 4
A[5] = 0<\/p>\n\n\n\n
-4 1
-1 4
0 4
0 5
2 6
5 8<\/p>\n\n\n\n
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<\/strong>: 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.<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
The right element is still smaller than the left one so nothing happens at this step. i becomes 3, j is the same, 5.<\/p>\n\n\n\n
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.<\/p>\n\n\n\nSolution<\/h2>\n\n\n\n
\/\/ you can write to stdout for debugging purposes, e.g.\n\/\/ console.log('this is a debug message');\n\n function sortAsc(a, b) {\n return (a - b)\n }\n \n function solution(A) {\n let counter = 0\n let j= 0;\n let leftLimit = [];\n let rightLimit = []\n \n \/\/fill the left and right limits of each circle\n for(var i=0; i < A.length; i++) {\n leftLimit[i] =i-A[i];\n rightLimit[i] =i+A[i];\n } \n\n \/\/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\n leftLimit.sort(sortAsc)\n rightLimit.sort(sortAsc)\n\n \/\/loop through all the elements of the RIGHT boundaries\n for(var i= 0; i<A.length; i++) {\n \/\/this is the tricky part to understand\n \/\/on the left we have the boundaries of open circles, on the right the boundary of the next circle\n \/\/as long as there are circles open (rightLimit[i] >= leftLimit[j]) and (j < A.length)\n while(j < A.length && rightLimit[i] >= leftLimit[j]){\n \/\/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 \n \/\/if j surpasses j, it means we overcalculated and we start to decrease the number of intersections \n counter += j-i;\n \/\/pass to the next open circle\n j++; \n } \n if(counter > 10000000) return -1;\n } \n \n return counter;\n }<\/code><\/pre>\n\n\n\n