Algorithm to calculate number of intersecting discs

O(N) complexity and O(N) memory solution.

private static int Intersections(int[] a)
{
    int result = 0;
    int[] dps = new int[a.length];
    int[] dpe = new int[a.length];

    for (int i = 0, t = a.length - 1; i < a.length; i++)
    {
        int s = i > a[i]? i - a[i]: 0;
        int e = t - i > a[i]? i + a[i]: t;
        dps[s]++;
        dpe[e]++;
    }

    int t = 0;
    for (int i = 0; i < a.length; i++)
    {
        if (dps[i] > 0)
        {
            result += t * dps[i];
            result += dps[i] * (dps[i] - 1) / 2;
            if (10000000 < result) return -1;
            t += dps[i];
        }
        t -= dpe[i];
    }

    return result;
}

So you want to find the number of intersections of the intervals [i-A[i], i+A[i]].

Maintain a sorted array (call it X) containing the i-A[i] (also have some extra space which has the value i+A[i] in there).

Now walk the array X, starting at the leftmost interval (i.e smallest i-A[i]).

For the current interval, do a binary search to see where the right end point of the interval (i.e. i+A[i]) will go (called the rank). Now you know that it intersects all the elements to the left.

Increment a counter with the rank and subtract current position (assuming one indexed) as we don't want to double count intervals and self intersections.

O(nlogn) time, O(n) space.