Codility - NumberOfDiscIntersections 100% I've been practicing some algorithm writing on the website codility.com. Specifically the task NumberOfDiscIntersections located here https://codility.com/programmers/lessons/4/ 

Here is the question: https://codility.com/programmers/task/number_of_disc_intersections/

I have a very efficient algorithm which solves it, but I only understand the first part. The second part is... math! And thus why I am posting here.

If you look in the code you'll see where I don't understand it. Can someone explain how one would come up with such an algorithm, I'd like to know (and a few other programmers too over at stackoverflow).

//  NumberOfDiscIntersections 100%
var A = [1, 5, 2, 1, 4, 0]; // should return 11

function solution(A) {
    var i,
        sum = 0,
        len = A.length,
        startArr = [],
        endArr = [],
        active = 0;

    // fill arrays with zeros
    for (i = 0; i &lt; len; i += 1) {
        startArr[i] = 0;
        endArr[i] = 0;
    }

    // sort start and end boundaries of the discs into their own arrays
    for (i = 0; i &lt; len; i += 1) {

        if (i &lt; A[i])
            startArr[0]++;
        else
            startArr[i - A[i]]++;

        if (i + A[i] &gt;= len)
            endArr[len - 1]++;
        else
            endArr[i + A[i]]++;
    }

    // &lt;--- here is where I lose it, this for loop, I just simply do not understand why this works or how anyone could of gotten this
    for (i = 0; i &lt; len; i += 1) {

        sum += active * startArr[i] + (startArr[i] * (startArr[i] - 1)) / 2;

        // over 10 000 000 return -1 as stated in the assignment
        if (10000000 &lt; sum)
            return -1;

        active += startArr[i] - endArr[i];
    }
    // return the answer
    return sum;
}

console.log(solution(A));
The for loop iterates through the positions on the line.

At iteration i, the "active" discs (call these the set $A_i$) are those discs who have started (that is, their left boundary is to the left of i) but not ended (that is, their right boundary is on or to the right of i).

The number startArr[i] describes the number of discs which are activated at position i (meaning their left boundary is on position i; call these the set $B_i$). 

It's clear that each of these discs in both sets mutually intersect. We know we have already counted the intersections of $A_i$ with itself. However, we do need to count the intersections of $A_i$ with $B_i$: this is the number active * startArr[i]. We also need to count the intersections of $B_i$ with itself: this is the number startArr[i] * (startArr[i] - 1) / 2 since $n*(n-1)/2$ is the number of ways to pick two things from a set of size $n$.

Finally, after adding these intersections, it updates the number of active discs. Indeed, the number of active discs is precisely the old number plus the ones which started at position i and minus the ones that ended at position i.



As to your question about how someone would "come up with this algorithm" -- I think that's a question that can have many answers and is definitely beyond the scope of this post.
I came up with a different solution. Another 100% solution that leverages counting by eliminating unnecessary steps. The core mentality of the algorithm is different. It just iterates on start and endpoints. I thought it's easier to understand because it only accumulates the connected discs on their ending point before removing them from the active list. I just wanted to share this solution too.
function solution(A) {
const startArr = {};
const endArr = {};

let min = Number.MAX_SAFE_INTEGER;
let max = Number.MIN_SAFE_INTEGER;

const indices = {};
for (let i = 0; i &lt; A.length; i++) {
  if (min &gt;= i - A[i]) {
    min = i - A[i];
  }

  if (max &lt; i + A[i]) {
    max = i + A[i];
  }

  if (startArr[`${i - A[i]}`] === undefined || startArr[`${i - A[i]}`] === null) {
    startArr[`${i - A[i]}`] = 1;
  } else {
    startArr[`${i - A[i]}`] += 1;
  }

  if (endArr[`${i + A[i]}`] === undefined || endArr[`${i + A[i]}`] === null) {
    endArr[`${i + A[i]}`] = 1;
  } else {
    endArr[`${i + A[i]}`] = endArr[`${i + A[i]}`] + 1;
  }
  indices[`${i - A[i]}`] = true;
  indices[`${i + A[i]}`] = true;
}

let currentStartedActive = 0;

let calcFinal = 0;

const allKeys = Object.keys(indices);
allKeys.sort(function(a, b){return a - b});

for (let i = 0; i &lt; allKeys.length; i++) {

  if (startArr[`${allKeys[i]}`] !== undefined &amp;&amp; startArr[`${allKeys[i]}`] !== null) {
    if (startArr[`${allKeys[i]}`] &gt; 0) {
      currentStartedActive += startArr[`${allKeys[i]}`];
    }
  }
  if (endArr[`${allKeys[i]}`] !== undefined &amp;&amp; endArr[`${allKeys[i]}`] !== null) {
    if (endArr[`${allKeys[i]}`] &gt; 0) {
      calcFinal += ((currentStartedActive - endArr[`${allKeys[i]}`]) * endArr[`${allKeys[i]}`]);

      const calculateInsider = endArr[`${allKeys[i]}`];

      if (calculateInsider &gt; 1) {
        calcFinal += ((calculateInsider * (calculateInsider - 1)) / 2);
      }
      if (calcFinal &gt; 10000000) {
        return -1;
      }
      currentStartedActive -= endArr[`${allKeys[i]}`];
    }
  }
}

return calcFinal;

}