Algorithm to calculate number of intersecting discs

Given an array A of N integers we draw N discs in a 2D plane, such that i-th disc has center in (0,i) and a radius A[i]. We say that k-th disc and j-th disc intersect, if k-th and j-th discs have at least one common point.

Write a function

int number_of_disc_intersections(int[] A);

which given an array A describing N discs as explained above, returns the number of pairs of intersecting discs. For example, given N=6 and

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

there are 11 pairs of intersecting discs:

0th and 1st
0th and 2nd
0th and 4th
1st and 2nd
1st and 3rd
1st and 4th
1st and 5th
2nd and 3rd
2nd and 4th
3rd and 4th
4th and 5th

so the function should return 11. The function should return -1 if the number of intersecting pairs exceeds 10,000,000. The function may assume that N does not exceed 10,000,000.

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.

Python 100 / 100 (tested) on codility, with O(nlogn) time and O(n) space.

Here is @noisyboiler's python implementation of @Aryabhatta's method with comments and an example. Full credit to original authors, any errors / poor wording are entirely my fault.

from bisect import bisect_right

def number_of_disc_intersections(A):
    pairs = 0
    
    # create an array of tuples, each containing the start and end indices of a disk
    # some indices may be less than 0 or greater than len(A), this is fine!
    # sort the array by the first entry of each tuple: the disk start indices
    intervals = sorted( [(i-A[i], i+A[i]) for i in range(len(A))] )

    # create an array of starting indices using tuples in intervals
    starts = [i[0] for i in intervals]

    # for each disk in order of the *starting* position of the disk, not the centre
    for i in range(len(starts)):

        # find the end position of that disk from the array of tuples
        disk_end = intervals[i][1]

        # find the index of the rightmost value less than or equal to the interval-end
        # this finds the number of disks that have started before disk i ends
        count = bisect_right(starts, disk_end )

        # subtract current position to exclude previous matches
        # this bit seemed 'magic' to me, so I think of it like this...
        # for disk i, i disks that start to the left have already been dealt with
        # subtract i from count to prevent double counting
        # subtract one more to prevent counting the disk itsself
        count -= (i+1)
        pairs += count
        if pairs > 10000000:
            return -1
    return pairs

Worked example: given [3, 0, 1, 6] the disk radii would look like this:

disk0  -------         start= -3, end= 3
disk1      .           start=  1, end= 1
disk2      ---         start=  1, end= 3
disk3  -------------   start= -3, end= 9
index  3210123456789   (digits left of zero are -ve)

intervals = [(-3, 3), (-3, 9), (1, 1), (1,3)]
starts    = [-3, -3, 1, 1]

the loop order will be: disk0, disk3, disk1, disk2

0th loop: 
    by the end of disk0, 4 disks have started 
    one of which is disk0 itself 
    none of which could have already been counted
    so add 3
1st loop: 
    by the end of disk3, 4 disks have started 
    one of which is disk3 itself
    one of which has already started to the left so is either counted OR would not overlap
    so add 2
2nd loop: 
    by the end of disk1, 4 disks have started 
    one of which is disk1 itself
    two of which have already started to the left so are either counted OR would not overlap
    so add 1
3rd loop: 
    by the end of disk2, 4 disks have started
    one of which is disk2 itself
    two of which have already started to the left so are either counted OR would not overlap
    so add 0

pairs = 6
to check: these are (0,1), (0,2), (0,2), (1,2), (1,3), (2,3),    

Well, I adapted Falk Hüffner's idea to c++, and made a change in the range. Opposite to what is written above, there is no need to go beyond the scope of the array (no matter how large are the values in it). On Codility this code received 100%. Thank you Falk for your great idea!

int number_of_disc_intersections ( const vector<int> &A ) {
    int sum=0;
	vector<int> start(A.size(),0);
	vector<int> end(A.size(),0);
	for (unsigned int i=0;i<A.size();i++){
		if ((int)i<A[i]) start[0]++;
		else		start[i-A[i]]++;
		if (i+A[i]>=A.size())	end[A.size()-1]++;
		else					end[i+A[i]]++;
	}
	int active=0;
	for (unsigned int i=0;i<A.size();i++){
		sum+=active*start[i]+(start[i]*(start[i]-1))/2;
		if (sum>10000000) return -1;
		active+=start[i]-end[i];
	}
	return sum;
}

This can even be done in linear time [EDIT: this is not linear time, see comments]. In fact, it becomes easier if you ignore the fact that there is exactly one interval centered at each point, and just treat it as a set of start- and endpoints of intervals. You can then just scan it from the left (Python code for simplicity):

from collections import defaultdict

a = [1, 5, 2, 1, 4, 0]

start = defaultdict(int)
stop = defaultdict(int)

for i in range(len(a)):
	start[i - a[i]] += 1
	stop[i + a[i]] += 1

active = 0
intersections = 0
for i in range(-len(a), len(a)):
	intersections += active * start[i] + (start[i] * (start[i] - 1)) / 2	
	active += start[i]
	active -= stop[i]

print intersections

Here's a O(N) time, O(N) space algorithm requiring 3 runs across the array and no sorting, verified scoring 100%:

You're interested in pairs of discs. Each pair involves one side of one disc and the other side of the other disc. Therefore we won't have duplicate pairs if we handle one side of each disc. Let's call the sides right and left (I rotated the space while thinking about it).

An overlap is either due to a right side overlapping another disc directly at the center (so pairs equal to the radius with some care about the array length) or due to the number of left sides existing at the rightmost edge.

So we create an array that contains the number of left sides at each point and then it's a simple sum.

C code:

int solution(int A[], int N) {
    int C[N];
    int a, S=0, t=0;
    
    // Mark left and middle of disks
    for (int i=0; i<N; i++) {
        C[i] = -1;
        a = A[i];
        if (a>=i) {
            C[0]++;
        } else {
            C[i-a]++;
        }
    }
    // Sum of left side of disks at location
    for (int i=0; i<N; i++) {
        t += C[i];
        C[i] = t;
    }
    // Count pairs, right side only:
    // 1. overlaps based on disk size
    // 2. overlaps based on disks but not centers
    for (int i=0; i<N; i++) {
        a = A[i];
        S += ((a<N-i) ? a: N-i-1);
        if (i != N-1) {
          S += C[((a<N-i) ? i+a: N-1)];
        }
        if (S>10000000) return -1;
    }
    return S;
}

I got 100 out of 100 with this C++ implementation:

#include <map>
#include <algorithm>

inline bool mySortFunction(pair<int,int> p1, pair<int,int> p2)
{
    return ( p1.first < p2.first );
}

int number_of_disc_intersections ( const vector<int> &A ) {
    int i, size = A.size();
    if ( size <= 1 ) return 0;
    // Compute lower boundary of all discs and sort them in ascending order
    vector< pair<int,int> > lowBounds(size);
    for(i=0; i<size; i++) lowBounds[i] = pair<int,int>(i-A[i],i+A[i]);
    sort(lowBounds.begin(), lowBounds.end(), mySortFunction);
    // Browse discs
    int nbIntersect = 0;
    for(i=0; i<size; i++)
    {
        int curBound = lowBounds[i].second;
        for(int j=i+1; j<size && lowBounds[j].first<=curBound; j++)
        {
            nbIntersect++;
            // Maximal number of intersections
            if ( nbIntersect > 10000000 ) return -1;
        }
    }
    return nbIntersect;
}

A Python answer

from bisect import bisect_right

def number_of_disc_intersections(li):
    pairs = 0
    # treat as a series of intervals on the y axis at x=0
    intervals = sorted( [(i-li[i], i+li[i]) for i in range(len(li))] )
    # do this by creating a list of start points of each interval
    starts = [i[0] for i in intervals]
    for i in range(len(starts)):
	    # find the index of the rightmost value less than or equal to the interval-end
	    count = bisect_right(starts, intervals[i][1])
	    # subtract current position to exclude previous matches, and subtract self
	    count -= (i+1)
	    pairs += count
	    if pairs > 10000000:
		    return -1
    return pairs

100/100 c#

  class Solution
    {
        class Interval
        {
            public long Left;
            public long Right;
        }

        public int solution(int[] A)
        {
            if (A == null || A.Length < 1)
            {
                return 0;
            }
            var itervals = new Interval[A.Length];
            for (int i = 0; i < A.Length; i++)
            {
                // use long to avoid data overflow (eg. int.MaxValue + 1)
                long radius = A[i];
                itervals[i] = new Interval()
                {
                    Left = i - radius,
                    Right = i + radius
                };
            }
            itervals = itervals.OrderBy(i => i.Left).ToArray();

            int result = 0;
            for (int i = 0; i < itervals.Length; i++)
            {
                var right = itervals[i].Right;
                for (int j = i + 1; j < itervals.Length && itervals[j].Left <= right; j++)
                {
                    result++;
                    if (result > 10000000)
                    {
                        return -1;
                    }
                }
            }
            return result;
        }
    }

Java 2*100%.

result is declared as long for a case codility doesn't test, namely 50k*50k intersections at one point.

class Solution {
	public int solution(int[] A) {
	
	    int[] westEnding = new int[A.length];
	    int[] eastEnding = new int[A.length];
	    
	    for (int i=0; i<A.length; i++) {
	   		if (i-A[i]>=0) eastEnding[i-A[i]]++; else eastEnding[0]++;
	   		if ((long)i+A[i]<A.length) westEnding[i+A[i]]++; else westEnding[A.length-1]++;
	    }
	    
	    long result = 0; //long to contain the case of 50k*50k. codility doesn't test for this.
	    int wests = 0;
	    int easts = 0;
	    for (int i=0; i<A.length; i++) {
	    	
	    	int balance = easts*wests; //these are calculated elsewhere
	    	
	   		wests++;
	    	easts+=eastEnding[i];

	   		result += (long) easts*wests - balance - 1; // 1 stands for the self-intersection
	   		if (result>10000000) return -1;
	   		
	    	easts--;
	   		wests-= westEnding[i];
	    }
	    
	    return (int) result;
	}
}

Swift 4 Solution 100% (Codility do not check the worst case for this solution)

public func solution(_ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)
    var count = 0
    let sortedA = A.sorted(by: >)
    if sortedA.isEmpty{ return 0 }
    let maxVal = sortedA[0]
    
    for i in 0..<A.count{
        let maxIndex = min(i + A[i] + maxVal + 1,A.count)
        for j in i + 1..<maxIndex{
            if j - A[j] <= i + A[i]{
                count += 1
            }
        }
        
        if count > 10_000_000{
            return -1
        }
    }
    
    return count
}

Here my JavaScript solution, based in other solutions in this thread but implemented in other languages.

function solution(A) {
    let circleEndpoints = [];
    
    for(const [index, num] of Object.entries(A)) {
        circleEndpoints.push([parseInt(index)-num, true]);
        circleEndpoints.push([parseInt(index)+num, false]);
    }
    
    circleEndpoints = circleEndpoints.sort(([a, openA], [b, openB]) => {
        if(a == b) return openA ? -1 : 1;
        return a - b;
    });
    
    let openCircles = 0;
    let intersections = 0;
    
    for(const [endpoint, opening] of circleEndpoints) {
        if(opening) {
            intersections += openCircles;
            openCircles ++;
        } else {
            openCircles --;
        }
        if(intersections > 10000000) return -1;
    }
    
    return intersections;
}

I'm offering one more solution because I did not find the counting principle of the previous solutions easy to follow. Though the results are the same, an explanation and more intuitive counting procedure seems worth presenting.

To begin, start by considering the O(N^2) solution that iterates over the discs in order of their center points, and counts the number of discs centered to the right of the current disc's that intersect the current disc, using the condition current_center + radius >= other_center - radius. Notice that we could get the same result counting discs centered to the left of the current disc using the condition current_center - radius <= other_center + radius.

def simple(A):
    """O(N^2) solution for validating more efficient solution."""
    N = len(A)
    unique_intersections = 0
    # Iterate over discs in order of their center positions 
    for j in range(N):
        # Iterate over discs whose center is to the right, to avoid double-counting.
        for k in range(j+1, N):
            # Increment cases where edge of current disk is at or right of the left edge of another disk.
            if j + A[j] >= k - A[k]:
                unique_intersections += 1
                # Stop early if we have enough intersections.
                # BUT: if the discs are small we still N^2 compare them all and time out.
                if unique_intersections > 10000000:
                    return -1
    return unique_intersections

We can go from O(N^2) to O(N) if we could only "look up" the number of discs to the right (or to the left!) that intersect the current disc. The key insight is to reinterpret the intersection condition as "the right edge of one disc overlaps the left edge of another disc", meaning (a ha!) the centers don't matter, only the edges.

The next insight is to try sorting the edges, taking O(N log N) time. Given a sorted array of the left edges and a sorted array of the right edges, as we scan our way from left to right along the number line, the number of left or right edges to the left of the current location point is simply the current index into left_edges and right_edges respectively: a constant-time deduction.

Finally, we use the "right edge > left edge" condition to deduce that the number of intersections between the current disc and discs that start only to the left of the current disc (to avoid duplicates) is the number of left edges to the left of the current edge, minus the number of right edges to the left of the current edge. That is, the number of discs starting to left of this one, minus the ones that closed already.

Now for this code, tested 100% on Codility:

def solution(A):
    """O(N log N) due to sorting, with O(N) pass over sorted arrays"""
    N = len(A)
    # Left edges of the discs, in increasing order of position.
    left_edges = sorted([(p-r) for (p,r) in enumerate(A)])
    # Right edges of the discs, in increasing order of position. 
    right_edges = sorted([(p+r) for (p,r) in enumerate(A)])
    #print("left edges:", left_edges[:10])
    #print("right edges:", right_edges[:10])
    intersections = 0
    right_i = 0
    # Iterate over the discs in order of their leftmost edge position.
    for left_i in range(N):
        # Find the first right_edge that's right of or equal to the current left_edge, naively:
        # right_i = bisect.bisect_left(right_edges, left_edges[left_i])
        # Just scan from previous index until right edge is at or beyond current left:
        while right_edges[right_i] < left_edges[left_i]:
             right_i += 1
        # Count number of discs starting left of current, minus the ones that already closed.
        intersections += left_i - right_i
        # Return early if we find more than 10 million intersections.
        if intersections > 10000000:
            return -1
    #print("correct:", simple(A))
    return intersections

count = 0
for (int i = 0; i < N; i++) {
  for (int j = i+1; j < N; j++) {
    if (i + A[i] >= j - A[j]) count++;
  }
}

It is O(N^2) so pretty slow, but it works.

This is a ruby solution that scored 100/100 on codility. I'm posting it now because I'm finding it difficult to follow the already posted ruby answer.

def solution(a)
    end_points = []
    a.each_with_index do |ai, i|
        end_points << [i - ai, i + ai]
    end
    end_points = end_points.sort_by { |points| points[0]}

    intersecting_pairs = 0
    end_points.each_with_index do |point, index|
        lep, hep = point
        pairs = bsearch(end_points, index, end_points.size - 1, hep)
        return -1 if 10000000 - pairs + index < intersecting_pairs
        intersecting_pairs += (pairs - index)
    end
    return intersecting_pairs
end

# This method returns the maximally appropriate position
# where the higher end-point may have been inserted.
def bsearch(a, l, u, x)
    if l == u
        if x >= a[u][0]
            return u
        else
            return l - 1 
        end
    end
    mid = (l + u)/2

    # Notice that we are searching in higher range
    # even if we have found equality.
    if a[mid][0] <= x
        return bsearch(a, mid+1, u, x)
    else
        return bsearch(a, l, mid, x)
    end
end

Probably extremely fast. O(N). But you need to check it out. 100% on Codility. Main idea:

1. At any point of the table, there are number of circles "opened" till the right edge of the circle, lets say "o".

2. So there are (o-1-used) possible pairs for the circle in that point. "used" means circle that have been processed and pairs for them counted.

   public int solution(int[] A) { final int N = A.length; final int M = N + 2; int[] left = new int[M]; // values of nb of "left" edges of the circles in that point int[] sleft = new int[M]; // prefix sum of left[] int il, ir; // index of the "left" and of the "right" edge of the circle

    for (int i = 0; i < N; i++) { // counting left edges
      il = tl(i, A);
      left[il]++;
    }
    
    sleft[0] = left[0];
    for (int i = 1; i < M; i++) {// counting prefix sums for future use
      sleft[i]=sleft[i-1]+left[i];
    }
    int o, pairs, total_p = 0, total_used=0;
    for (int i = 0; i < N; i++) { // counting pairs
      ir = tr(i, A, M);
      o  = sleft[ir];                // nb of open till right edge
      pairs  = o -1 - total_used;
      total_used++;
      total_p += pairs;
    }
    if(total_p > 10000000){
      total_p = -1;
    }
    return total_p;
   

   }

    private int tl(int i, int[] A){
    int tl = i - A[i]; // index of "begin" of the circle
      if (tl < 0) {
        tl = 0;
      } else {
        tl = i - A[i] + 1;
      }
    return tl;
   

   } int tr(int i, int[] A, int M){ int tr; // index of "end" of the circle if (Integer.MAX_VALUE - i < A[i] || i + A[i] >= M - 1) { tr = M - 1; } else { tr = i + A[i] + 1; } return tr; }

There are a lot of great answers here already, including the great explanation from the accepted answer. However, I wanted to point out a small observation about implementation details in the Python language.

Originally, I've came up with the solution shown below. I was expecting to get O(N*log(N)) time complexity as soon as we have a single for-loop with N iterations, and each iteration performs a binary search that takes at most log(N).

def solution(a):
    import bisect
    if len(a) <= 1:
        return 0
    cuts = [(c - r, c + r) for c, r in enumerate(a)]
    cuts.sort(key=lambda pair: pair[0])
    lefts, rights = zip(*cuts)
    n = len(cuts)
    total = 0
    for i in range(n):
        r = rights[i]
        pos = bisect.bisect_right(lefts[i+1:], r)
        total += pos
        if total > 10e6:
            return -1
    return total

However, I've get O(N**2) and a timeout failure. Do you see what is wrong here? Right, this line:

pos = bisect.bisect_right(lefts[i+1:], r)

In this line, you are actually taking a copy of the original list to pass it into binary search function, and it totally ruins the efficiency of the proposed solution! It makes your code just a bit more consice (i.e., you don't need to write pos - i - 1) but heavily undermies the performance. So, as it was shown above, the solution should be:

def solution(a):
    import bisect
    if len(a) <= 1:
        return 0
    cuts = [(c - r, c + r) for c, r in enumerate(a)]
    cuts.sort(key=lambda pair: pair[0])
    lefts, rights = zip(*cuts)
    n = len(cuts)
    total = 0
    for i in range(n):
        r = rights[i]
        pos = bisect.bisect_right(lefts, r)
        total += (pos - i - 1)
        if total > 10e6:
            return -1
    return total

It seems that sometimes one could be too eager about making slices and copies because Python allows you to do it so easily :) Probably not a great insight, but for me it was a good lesson to pay more attention to these "technical" moments when converting ideas and algorithms into real-word solutions.

I know that this is an old questions but it is still active on codility.

    private int solution(int[] A)
    {
        int openedCircles = 0;
        int intersectCount = 0;

We need circles with their start and end values. For that purpose I have used Tuple. True/False indicates if we are adding Circle Starting or Circle Ending value.

        List<Tuple<decimal, bool>> circles = new List<Tuple<decimal, bool>>();
        for(int i = 0; i < A.Length; i ++)
        {
            // Circle start value
            circles.Add(new Tuple<decimal, bool>((decimal)i - (decimal)A[i], true));

            // Circle end value
            circles.Add(new Tuple<decimal, bool>((decimal)i + (decimal)A[i], false));
        }

Order "circles" by their values. If one circle is ending at same value where other circle is starting, it should be counted as intersect (because of that "opening" should be in front of "closing" if in same point)

        circles = circles.OrderBy(x => x.Item1).ThenByDescending(x => x.Item2).ToList();

Counting and returning counter

        foreach (var circle in circles)
        {
            // We are opening new circle (within existing circles)
            if(circle.Item2 == true)
            {
                intersectCount += openedCircles;

                if (intersectCount > 10000000)
                { 
                    return -1;
                }

                openedCircles++;
            }
            else
            {
                // We are closing circle
                openedCircles--;
            }
        }

        return intersectCount;
    }

Javascript solution 100/100 based on this video https://www.youtube.com/watch?v=HV8tzIiidSw

function sortArray(A) {
    return A.sort((a, b) => a - b)
}

function getDiskPoints(A) {
    const diskStarPoint = []
    const diskEndPoint = []
    for(i = 0; i < A.length; i++) {
        diskStarPoint.push(i - A[i])
        diskEndPoint.push(i + A[i])
    }
    return {
        diskStarPoint: sortArray(diskStarPoint),
        diskEndPoint: sortArray(diskEndPoint)
    };
}

function solution(A) {
    const { diskStarPoint, diskEndPoint } = getDiskPoints(A)
    let index = 0;
    let openDisks = 0;
    let intersections = 0;
    for(i = 0; i < diskStarPoint.length; i++) {
      while(diskStarPoint[i] > diskEndPoint[index]) {
        openDisks--
        index++
      }
      intersections += openDisks
      openDisks++
    }
    return intersections > 10000000 ? -1 : intersections
}

This got 100/100 in c#

class CodilityDemo3
{

    public static int GetIntersections(int[] A)
    {
        if (A == null)
        {
            return 0;
        }

        int size = A.Length;

        if (size <= 1)
        {
            return 0;
        }

        List<Line> lines = new List<Line>();

        for (int i = 0; i < size; i++)
        {
            if (A[i] >= 0)
            {
                lines.Add(new Line(i - A[i], i + A[i]));
            }
        }

        lines.Sort(Line.CompareLines);
        size = lines.Count;
        int intersects = 0;

        for (int i = 0; i < size; i++)
        {
            Line ln1 = lines[i];
            for (int j = i + 1; j < size; j++)
            {
                Line ln2 = lines[j];
                if (ln2.YStart <= ln1.YEnd)
                {
                    intersects += 1;
                    if (intersects > 10000000)
                    {
                        return -1;
                    }
                }
                else
                {
                    break;
                }
            }
        }

        return intersects;
    }

}

public class Line
{
    public Line(double ystart, double yend)
    {
        YStart = ystart;
        YEnd = yend;
    }
    public double YStart { get; set; }
    public double YEnd { get; set; }

    public static int CompareLines(Line line1, Line line2)
    {
        return (line1.YStart.CompareTo(line2.YStart));

    }
}

}

Thanks to Falk for the great idea! Here is a ruby implementation that takes advantage of sparseness.

def int(a)

    event = Hash.new{|h,k| h[k] = {:start => 0, :stop => 0}}
    a.each_index {|i|
        event[i - a[i]][:start] += 1
        event[i + a[i]][:stop ] += 1
    }
    sorted_events = (event.sort_by {|index, value| index}).map! {|n| n[1]}

    past_start = 0
    intersect = 0

    sorted_events.each {|e|

        intersect += e[:start] * (e[:start]-1) / 2 +
                     e[:start] * past_start

        past_start += e[:start]
        past_start -= e[:stop]
    }
    return intersect
end

puts int [1,1]

puts int [1,5,2,1,4,0]

Here is the PHP code that scored 100 on codility:

$sum=0;

//One way of cloning the A:
$start = array();
$end = array();

foreach ($A as $key=>$value)
{
$start[]=0;
$end[]=0;  	
}  

for ($i=0; $i<count($A); $i++)
{
  if ($i<$A[$i]) 
  $start[0]++;
  else        
  $start[$i-$A[$i]]++;
  
  if ($i+$A[$i] >= count($A))   
  $end[count($A)-1]++;
  else
  $end[$i+$A[$i]]++;
}
$active=0;
for ($i=0; $i<count($A);$i++)
{
  $sum += $active*$start[$i]+($start[$i]*($start[$i]-1))/2;
  if ($sum>10000000) return -1;
  $active += $start[$i]-$end[$i];
}
return $sum;

However I dont understand the logic. This is just transformed C++ code from above. Folks, can you elaborate on what you were doing here, please?

#include <stdio.h>
#include <stdlib.h>
void sortPairs(int bounds[], int len){
	int i,j, temp;
	for(i=0;i<(len-1);i++){
		for(j=i+1;j<len;j++){
			if(bounds[i] > bounds[j]){
				temp = bounds[i];
				bounds[i] = bounds[j];
				bounds[j] = temp;
				temp = bounds[i+len];
				bounds[i+len] = bounds[j+len];
				bounds[j+len] = temp;
			}
		}
	}
}
int adjacentPointPairsCount(int a[], int len){
	int count=0,i,j;
	int *bounds;
	if(len<2) {
		goto toend;
	}
	bounds = malloc(sizeof(int)*len *2);
	for(i=0; i< len; i++){
		bounds[i] = i-a[i];
		bounds[i+len] = i+a[i];
	}
	sortPairs(bounds, len);
	for(i=0;i<len;i++){
		int currentBound = bounds[i+len];
		for(j=i+1;a[j]<=currentBound;j++){
			if(count>100000){
				count=-1;
				goto toend;
			}
			count++;
		}     
	}
toend:
	free(bounds);
	return count;   
}

An Implementation of Idea stated above in Java:

public class DiscIntersectionCount {


public int number_of_disc_intersections(int[] A) {
	int[] leftPoints = new int[A.length];
	for (int i = 0; i < A.length; i++) {
		leftPoints[i] = i - A[i];
	}
	
	Arrays.sort(leftPoints);
//		System.out.println(Arrays.toString(leftPoints));
	int count  = 0;
	for (int i = 0; i < A.length - 1; i++) {
		int rpoint = A[i] + i;

		int rrank = getRank(leftPoints, rpoint);
		
		//if disk has sifnificant radius, exclude own self
		if (rpoint > i) rrank -= 1;
		int rank = rrank; 
//			System.out.println(rpoint+" : "+rank);

		rank -= i;
		count += rank;
	}
	return count;
	
}

public int getRank(int A[], int num) {
	if (A==null || A.length == 0) return -1;		
	int mid = A.length/2;
	while ((mid >= 0) && (mid < A.length)) {
		
		if (A[mid] == num) return mid;
		
		if ((mid == 0) && (A[mid] > num)) return -1;
		if ((mid == (A.length - 1)) && (A[mid] < num)) return A.length;
		if (A[mid] < num && A[mid + 1] >= num) return mid + 1;
		if (A[mid] > num && A[mid - 1] <= num) return mid - 1;
		
		if (A[mid] < num) mid = (mid + A.length)/2;
		else  mid = (mid)/2;
		
	}
	
	return -1;
}

public static void main(String[] args) {
	DiscIntersectionCount d = new DiscIntersectionCount();
	int[] A = 
		//{1,5,2,1,4,0}
	 	//{0,0,0,0,0,0}
	//	{1,1,2}
	{3}
	 ;
	int count = d.number_of_disc_intersections(A);
	System.out.println(count);
}
}

A 100/100 C# implementation as described by Aryabhatta (the binary search solution).

using System;

class Solution {
    public int solution(int[] A)
	{
        return IntersectingDiscs.Execute(A);
    }
}

class IntersectingDiscs
{
	public static int Execute(int[] data)
	{
		int counter = 0;

		var intervals = Interval.GetIntervals(data);

		Array.Sort(intervals); // sort by Left value

		for (int i = 0; i < intervals.Length; i++)
		{
			counter += GetCoverage(intervals, i);

			if(counter > 10000000)
			{
				return -1;
			}
		}

		return counter;
	}

	private static int GetCoverage(Interval[] intervals, int i)
	{
		var currentInterval = intervals[i];

		// search for an interval starting at currentInterval.Right

		int j = Array.BinarySearch(intervals, new Interval { Left = currentInterval.Right });

		if(j < 0)
		{
			// item not found

			j = ~j; // bitwise complement (see Array.BinarySearch documentation)

			// now j == index of the next item larger than the searched one

			j = j - 1; // set index to the previous element
		}

		while(j + 1 < intervals.Length && intervals[j].Left == intervals[j + 1].Left)
		{
			j++; // get the rightmost interval starting from currentInterval.Righ
		}

		return j - i; // reduce already processed intervals (the left side from currentInterval)
	}
}

class Interval : IComparable
{
	public long Left { get; set; }
	public long Right { get; set; }

	// Implementation of IComparable interface
	// which is used by Array.Sort().
	public int CompareTo(object obj)
	{
		// elements will be sorted by Left value

		var another = obj as Interval;

		if (this.Left < another.Left)
		{
			return -1;
		}

		if (this.Left > another.Left)
		{
			return 1;
		}

		return 0;
	}

	/// <summary>
	/// Transform array items into Intervals (eg. {1, 2, 4} -> {[-1,1], [-1,3], [-2,6]}).
	/// </summary>
	public static Interval[] GetIntervals(int[] data)
	{
		var intervals = new Interval[data.Length];

		for (int i = 0; i < data.Length; i++)
		{
			// use long to avoid data overflow (eg. int.MaxValue + 1)
			
			long radius = data[i];

			intervals[i] = new Interval
			{
				Left = i - radius,
				Right = i + radius
			};
		}

		return intervals;
	}
}

100% score in Codility.

Here is an adaptation to C# of Толя solution:

    public int solution(int[] A)
    {
        long result = 0;
        Dictionary<long, int> dps = new Dictionary<long, int>();
        Dictionary<long, int> dpe = new Dictionary<long, int>();

        for (int i = 0; i < A.Length; i++)
        {
            Inc(dps, Math.Max(0, i - A[i]));
            Inc(dpe, Math.Min(A.Length - 1, i + A[i]));
        }

        long t = 0;
        for (int i = 0; i < A.Length; i++)
        {
            int value;
            if (dps.TryGetValue(i, out value))
            {
                result += t * value;
                result += value * (value - 1) / 2;
                t += value;
                if (result > 10000000)
                    return -1;
            }
            dpe.TryGetValue(i, out value);
            t -= value;
        }

        return (int)result;
    }

    private static void Inc(Dictionary<long, int> values, long index)
    {
        int value;
        values.TryGetValue(index, out value);
        values[index] = ++value;
    }

Here's a two-pass C++ solution that doesn't require any libraries, binary searching, sorting, etc.

int solution(vector<int> &A) {
    #define countmax 10000000
    int count = 0;
    // init lower edge array
    vector<int> E(A.size());
    for (int i = 0; i < (int) E.size(); i++)
        E[i] = 0;
    // first pass
    // count all lower numbered discs inside this one
    // mark lower edge of each disc
    for (int i = 0; i < (int) A.size(); i++)
    {
        // if disc overlaps zero
        if (i - A[i] <= 0)
            count += i;
        // doesn't overlap zero
        else {   
            count += A[i];
            E[i - A[i]]++;
        }
        if (count > countmax)
            return -1;
    }
    // second pass
    // count higher numbered discs with edge inside this one
    for (int i = 0; i < (int) A.size(); i++)
    {
        // loop up inside this disc until top of vector
        int jend = ((int) E.size() < (long long) i + A[i] + 1 ? 
                    (int) E.size() : i + A[i] + 1);
        // count all discs with edge inside this disc
        // note: if higher disc is so big that edge is at or below 
        // this disc center, would count intersection in first pass
        for (int j = i + 1; j < jend; j++)
            count += E[j];
        if (count > countmax)
            return -1;
    }
    return count;
}

My answer in Swift; gets a 100% score.

import Glibc

struct Interval {
    let start: Int
    let end: Int
}

func bisectRight(intervals: [Interval], end: Int) -> Int {
    var pos = -1
    var startpos = 0
    var endpos = intervals.count - 1
    
    if intervals.count == 1 {
        if intervals[0].start < end {
            return 1
        } else {
            return 0
        }
    }
    
    while true {
        let currentLength = endpos - startpos
        
        if currentLength == 1 {
            pos = startpos
            pos += 1
            if intervals[pos].start <= end {
                pos += 1
            }
            break
        } else {
            let middle = Int(ceil( Double((endpos - startpos)) / 2.0 ))
            let middlepos = startpos + middle
            
            if intervals[middlepos].start <= end {
                startpos = middlepos
            } else {
                endpos = middlepos
            }
        }
    }
    
    return pos
}

public func solution(inout A: [Int]) -> Int {
    let N = A.count
    var nIntersections = 0
    
    // Create array of intervals
    var unsortedIntervals: [Interval] = []
    for i in 0 ..< N {
        let interval = Interval(start: i-A[i], end: i+A[i])
        unsortedIntervals.append(interval)
    }
    
    // Sort array
    let intervals = unsortedIntervals.sort {
        $0.start < $1.start
    }
    
    for i in 0 ..< intervals.count {
        let end = intervals[i].end
        
        var count = bisectRight(intervals, end: end)
        
        count -= (i + 1)
        nIntersections += count
        
        if nIntersections > Int(10E6) {
            return -1
        }
    }
    
    return nIntersections
}

C# solution 100/100

using System.Linq;

class Solution
{
    private struct Interval
    {
        public Interval(long @from, long to)
        {
            From = @from;
            To = to;
        }

        public long From { get; }
        public long To { get; }
    }

    public int solution(int[] A)
    {
        int result = 0;

        Interval[] intervals = A.Select((value, i) =>
        {
            long iL = i;
            return new Interval(iL - value, iL + value);
        })
        .OrderBy(x => x.From)
        .ToArray();

        for (int i = 0; i < intervals.Length; i++)
        {
            for (int j = i + 1; j < intervals.Length && intervals[j].From <= intervals[i].To; j++)
                result++;

            if (result > 10000000)
                return -1;
        }

        return result;
    }
}

A ruby solution. Scores 100%.

def solution(a)
  # write your code in Ruby 2.2
  open = Hash.new
  close = Hash.new
  
  (0..(a.length-1)).each do |c|
    r = a[c]
    open[ c-r ]  ? open[ c-r ]+=1  : open[ c-r ]=1
    close[ c+r ] ? close[ c+r ]+=1 : close[ c+r ]=1 
  end
  
  open_now = 0
  intersections = 0
  open.merge(close).keys.sort.each do |v|
    intersections += (open[v]||0)*open_now
    open_now += (open[v]||0) - (close[v]||0)
    if(open[v]||0)>1
      # sum the intersections of only newly open discs
      intersections += (open[v]*(open[v]-1))/2
      return -1 if intersections > 10000000
    end
  end
  intersections
end

C# 100/100 with O(N*log(N)) time complexity and O(N) space complexity.

The main ideas:

1. Make 2 sorted arrays: left points and right points.
2. Merge these arrays into one boolean array where true means "opening" and false means "closing" an interval.
3. Run through the boolean array and count opened intervals, sum them up.

_

public int solution(int[] A) 
{        
    var sortedStartPoints = A.Select((value, index) => (long)index-value).OrderBy(i => i).ToArray();
    var sortedEndPoints = A.Select((value, index) => (long)index+value).OrderBy(i => i).ToArray();     
          
    // true - increment, false - decrement, null - stop
    var points = new bool?[2*A.Length];

    // merge arrays
    for(int s=0, e=0, p=0; p < points.Length && s < sortedStartPoints.Length; p++)
    {
        long startPoint = sortedStartPoints[s];
        long endPoint = sortedEndPoints[e];
        if(startPoint <= endPoint)
        {
            points[p] = true;
            s++;
        }
        else
        {
            points[p] = false;
            e++;
        }
    }

    int result = 0;
    int opened = 0;
    // calculate intersections
    foreach(bool? p in points.TakeWhile(_ => _.HasValue))
    {
        if(result > 10000000)
            return -1;
            
        if(p == true)
        {
            result += opened;
            opened++;
        }
        else
        {                
            opened--;
        }
    }
    
    return result;
}

Below is an implementation of the accepted answer by @Aryabhatta in Kotlin so all the credit goes @Aryabhatta

fun calculateDiscIntersections(A: Array<Int>): Int {
    val MAX_PAIRS_ALLOWED = 10_000_000L
    //calculate startX and endX for each disc
    //as y is always 0 so we don't care about it. We only need X
    val ranges = Array(A.size) { i ->
        calculateXRange(i, A[i])
    }

    //sort Xranges by the startX
    ranges.sortBy { range ->
        range.start
    }

    val starts = Array(ranges.size) {index ->
        ranges[index].start
    }

    var count = 0
    for (i in 0 until ranges.size) {
        val checkRange = ranges[i]

        //find the right most disc whose start is less than or equal to end of current disc
        val index = bisectRight(starts, checkRange.endInclusive, i)

        //the number of discs covered by this disc are:
        //count(the next disc/range ... to the last disc/range covered by given disc/range)
        //example: given disc index = 3, last covered (by given disc) disc index = 5
        //count = 5 - 3 = 2
        //because there are only 2 discs covered by given disc
        // (immediate next disc with index 4 and last covered disc at index 5)
        val intersections = (index - i)

        //because we are only considering discs intersecting/covered by a given disc to the right side
        //and ignore any discs that are intersecting on left (because previous discs have already counted those
        // when checking for their right intersects) so this calculation avoids any duplications
        count += intersections

        if (count > MAX_PAIRS_ALLOWED) {
            return -1
        }
    }

    return if (count > MAX_PAIRS_ALLOWED) {
        -1
    } else {
        count
    }
}

private fun calculateXRange(x: Int, r: Int): LongRange {
    val minX = x - r.toLong()
    val maxX = x + r.toLong()

    return LongRange(minX, maxX)
}

fun bisectRight(array: Array<Long>, key: Long, arrayStart: Int = 0): Int {
    var start = arrayStart
    var end = array.size - 1
    var bisect = start

    while (start <= end) {
        val mid = Math.ceil((start + end) / 2.0).toInt()
        val midValue = array[mid]
        val indexAfterMid = mid + 1

        if (key >= midValue) {
            bisect = mid
        }

        if (key >= midValue && (indexAfterMid > end || key < array[indexAfterMid])) {
            break
        } else if (key < midValue) {
            end = mid - 1
        } else {
            start = mid + 1
        }
    }

    return bisect
}

Codility Solution with 100% score.

Here's my clean solution in Python (without importing libraries). This logic can be adapted to any other programming language.

I got a 100% in Codility - Time: O(Nlog(N)) - Space: O(N)

I hope it helps.

def solution(A):
  start, end = [], []
  for i, val in enumerate(A):
    start.append(i-val)
    end.append(i+val)
    
  start.sort()
  end.sort()
  
  count, currCircles, aux1, aux2 = 0, 0, 0, 0
  while aux1 != len(start) and aux2 != len(end):
    if aux1 < len(start) and start[aux1] <= end[aux2]:
      count += currCircles
      currCircles +=1
      aux1 +=1
      if currCircles > 10000000:
          return -1
    else:
      currCircles -=1
      aux2 +=1
  
  return count

 const endpoints = [];
    A.map((val, index) => {
        endpoints.push([index - val, 'S']);
        endpoints.push([index + val, 'E']);
    });
    endpoints.sort((a, b) => {
        if (a[0] < b[0]) {
            return -1;
        }
        if (a[0] > b[0]) {
            return 1;
        }
        if (a[0] === b[0] && a[1] === 'S')
            return -1;
        else
            return 1;
    });

    let count = 0;
    let intersections = 0;
    let point = [];
    const length = endpoints.length;
    for (let i = 0; i < length; i++) {
        point = endpoints[i];
        if (point[1] === 'S') {
            count += intersections;
            intersections += 1
        } else {
            intersections -= 1;
        }
        if (intersections > 10e6)
            return -1;
    }
    return count;

O(N*logN) 100%/100%

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        long[] startPositionList = new long[A.length];
        long[] finishPositionList = new long[A.length];
        for (int i = 0; i < A.length; i++) {
            // (long), because otherwise number 2,147,483,647 will overflow
            startPositionList[i] = (long)i - A[i];
            finishPositionList[i] = (long)i + A[i];
        }
        
        Arrays.sort(startPositionList);
        Arrays.sort(finishPositionList);
        
        int count = 0;
        int multiplier = 0;
        int startIndex = 0;
        int finishIndex = 0;
        // After we passed through all start positions, our solution won't change, hence we can stop the loop
        while (startIndex < A.length) {
            if (startPositionList[startIndex] > finishPositionList[finishIndex]) {
                // Finish position is next smallest
                multiplier--;
                finishIndex++;
            } else {
                // Start position is next smallest or is equal to finish position
                count += multiplier;
                multiplier++;
                startIndex++;
                // There is a condition to return -1 if count is bigger than 1e7
                if (count > (int)1e7) {
                    return -1;
                }
            }
        }
        
        return count;
    }
}

The golang solution, because codility only supports go up to v1.4, we have to implement the Sorter interface manually to sort a 2-tuple array;

package solution

// you can also use imports, for example:
// import "fmt"
import "sort"

// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")

type Circle struct {
	left, right int
}

type CircleSorter []*Circle

func (cs CircleSorter) Len() int {
	return len(cs)
}

func (cs CircleSorter) Swap(i, j int) {
	cs[i], cs[j] = cs[j], cs[i]
}

func (cs CircleSorter) Less(i, j int) bool {
	return cs[i].left < cs[j].left
}

func BiSecRight(data []*Circle, target int) int {
	return sort.Search(len(data), func(i int) bool {
		return data[i].left > target
	})
}

func Solution(A []int) int {
	data := make([]*Circle, len(A))
	for i := 0; i < len(A); i++ {
		data[i] = &Circle{
			left:  i - A[i],
			right: i + A[i],
		}
	}

	sort.Sort(CircleSorter(data))

	count := 0

	for i, v := range data {
		count += BiSecRight(data, v.right) - 1 - i
	}
	
	if count > 10000000 {
	    count = -1
	}
	
	return count
}

If you draw these discs on a paper, you can intuitively assume that it's sorted by the left end of each disc. For each disc, see how much the right end reaches over other discs, that is - intersects the other discs left ends and stop checking there. This stopping saves time that we would have spent in the most trivial solution of O(n * n) and instead get something like O(n*log(n)). Not as efficient as some O(n) solutions here, but it's a simple and understandable code that is efficient enough for 100% on codility submission. While solving this, I did take inspiration from posts by noisyboiler and GnomeDePlume

The language is Javascript

function solution(A) {

    //for each disk, create an array of objects containing left and right ends, then sort it by the left end. 
    const B = A.map((a, i) => ({ left: i - a, right: i + a })).sort((a, b) => a.left - b.left)
    let count = 0
    //index i is the disk we are testing intersection with any disc j
    for (let i = 0; i < B.length - 1; i++) {
        for (let j = i + 1; j < B.length; j++) {
            if (B[i].right >= B[j].left) {
                count++;
                //this is just an explicit condition for the codility task
                if (count > 10000000) return -1
            }
            else break;
            //since the array is sorted by the left ends, we know that we won't find any disk that the right side of disc i would reach
        }
    }
    return count
}

Similar to other answers (C++), though slightly different, short and explained. Linear in both space and time, and 100% on codility.

Let's first define the following rules:

1. If you open N discs at point X (that is, N discs start their uttermost left position at index X), then all those discs intersect each other. We cannot count double intersections (disc 1 intersects 2 and disc 2 intersects 1 = 1 intersection, not 2). So, the formula to calculate the intersections is: N (N - 1)/2 (easy to check manually).
2. At point X + 1 you open another set of M discs. We use the formula of point 1, and since we did not close any of the previous discs, we add M * N intersections (also easy to check manually).
3. If at X + 1, we had closed C discs, then the formula of point 2 would be M * (N - C), where N - C is the number of already opened discs at point X + 1 (without counting the new ones - M).

So, in this code we are first going to determine how many discs start and end at each position (0 to A.size() - 1). Then we are updating the intersections by means of the formulas above. It is important where you update the openDiscs counter in order to compute correctly the formula of point 3.

    int solution(vector<int> &A) {
        // count start/end points at each position
        std::vector<size_t> starts(A.size(), 0);
        std::vector<size_t> ends(A.size(), 0);
        for (size_t idx = 0; idx < A.size(); ++idx)
        {
            // make sure not to have overflow here
            size_t s = std::max<int>(0, idx - A[idx]);
            size_t e = std::min<size_t>(A.size() - 1, idx + A[idx]);
        
            ++starts[s];
            ++ends[e];
        }
        // starts[idx] is a counter which indicates how many discs have their uttermost left point at idx
        // ends[idx] is a counter which indicates how many discs have their uttermost right point at idx

        // loop over lines and count intersections (make sure no overflow)
        unsigned long int openDiscs = 0;
        unsigned long int intersections = 0;
        for (size_t idx = 0; idx < A.size(); ++idx)
        {
            // intersections due to newly opened discs (point 1)
            intersections += starts[idx] * (starts[idx] - 1) / 2;
        
            // intersections due to previously opened discs (point 2, 3)
            intersections += openDiscs * starts[idx];
        
            // update open discs
            openDiscs += starts[idx] - ends[idx];
        
            if (intersections > 10000000) return -1;
        }
    
        return intersections;
    }

This is an O(N) time O(N) space solution. No sorting is necessary. This solution scored 100% on Codility.

function solution(A) {
  // write your code in JavaScript (Node.js 8.9.4)
  let totalUniquePairs = 0;
  
  if (A.length === 0) return 0;
  
  // array contain counts of how many circles begin at that index
  const opens = new Array(A.length).fill(0);
  // array containg counts of how many circles stop at that index
  const closes = new Array(A.length).fill(0);
  
  // populate the open/closes
  for (let i = 0; i < A.length; ++i) {
      const radius = A[i];
      // keep this within the bounds of the array
      const opensAt = Math.max(0, i - radius);
      const closesAt = Math.min(A.length - 1, i + radius);
      ++closes[closesAt];
      ++opens[opensAt];
  }

  
  // operate in sort of a stack fashion
  let overlapping = 0;
  for (let i = 0; i < A.length; ++i) {
      const opening = opens[i];
      const closing = closes[i];
      overlapping += opening;
      
      if (closing <= 0) continue; // no closing, no new pairs

      // naive way
      // for (let j = 0; j < closing; ++j) {
      //     // overlapping - 1 = possible unique pairs here
      //     totalUniquePairs += overlapping - 1;
      //     if (totalUniquePairs > 10000000) return -1;
      //     overlapping -= 1;
      // }
      
      // optimized way
      // summation pattern from 1 to some number k
      // closes = 3 => totalUniquePairs += (overlapping - 1) + (overlapping - 2) + (overlapping - 3);
      // ^ can be simplified as totalUniquePairs += (overlapping * k) - (k * (k + 1) / 2);
      // https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF
      totalUniquePairs += (overlapping * closing) - (closing * (closing + 1) / 2);
      if (totalUniquePairs > 10000000) return -1;
      overlapping -= closing;
  }
  
  
  return totalUniquePairs;
}

The way this algo works, is by tracking the number of intersecting circles u are dealing with at the index you are processing.

When you close a circle u are tracking, you can count the number of unique pairs formed by the closing circle and the ones that are intersecting. The number of unique pairs is the number of current intersecting circles - 1. U then remove this circle from the number of intersecting circles you are tracking at the index and you can repeat this pattern for every circle that closes at that index.

This is akin to popping off equations you need to process in a stack when you have to deal with parenthesis.

So we only need to expend memory for two things:

• how many circles open at this index i? opens Array handles this
• how many circles open at this index i? closes Array handles this

Javascript solution costing O(N*log(N)) time & O(N) space.

function solution(A) {
  const start = [];
  const end = [];

  A.forEach((radius, index) => {
    start.push(index - radius);
    end.push(index + radius);
  });

  start.sort((a, b) => a - b);
  end.sort((a, b) => a - b);

  let intersections = 0;
  let open = 0;

  let i = 0;
  let j = 0;

  while (i < start.length) {
    if (start[i] <= end[j]) {
      intersections += open;
      if (intersections > 10000000) {
        return -1;
      }
      open++;
      i++;
    } else {
      open--;
      j++;
    }
  }

  return intersections;
}

enter code here

This is what I did... It gives 100% performance and 93% correctness(because of one test "arithmetic overflow tests" failed.

public static int NumberOfDiscIntersections(int[] A)
    {
        int[] leftEdges = new int[A.Length];
        int[] rightEdges = new int[A.Length];
        int openDisc = 0;
        int intersect = 0;
        int leftEdgeIndex = 0;
        for (int i = 0; i < A.Length; i++)
        {
            leftEdges[i] = i - A[i];
            rightEdges[i] = i + A[i];
        }
        Array.Sort(leftEdges);
        Array.Sort(rightEdges);

        for (int j = 0; j < rightEdges.Length; j++)
        {
            for (int i = leftEdgeIndex; i < leftEdges.Length; i++)
            {
                if (leftEdges[i] <= rightEdges[j])
                {
                    intersect += openDisc;
                    openDisc += 1;
                    leftEdgeIndex += 1;
                }
                else
                {
                    openDisc -= 1;
                    break;
                }
                if (intersect > 10000000) return -1;
            }
            if(leftEdgeIndex == leftEdges.Length)
            {
                break; //All Left Edges are opened, So all Intersect calculated
            }                
        }
        return intersect;
    }

so, I was doing this test in Scala and I would like to share here my example. My idea to solve is:

Extract the limits to the left and right of each position on the array.

A[0] = 1 --> (0-1, 0+1) = A0(-1, 1)
A[1] = 5 --> (1-5, 1+5) = A1(-4, 6)
A[2] = 2 --> (2-2, 2+2) = A2(0, 4)
A[3] = 1 --> (3-1, 3+1) = A3(2, 4)
A[4] = 4 --> (4-4, 4+4) = A4(0, 8)
A[5] = 0 --> (5-0, 5+0) = A5(5, 5)

Check if there is intersections between any two positions

(A0_0 >= A1_0 AND A0_0 <= A1_1) OR // intersection
(A0_1 >= A1_0 AND A0_1 <= A1_1) OR // intersection
(A0_0 <= A1_0 AND A0_1 >= A1_1)    // one circle contain inside the other

if any of these two checks is true count one intersection.

object NumberOfDiscIntersections {
  def solution(a: Array[Int]): Int = {
    var count: Long = 0
    for (posI: Long <- 0L until a.size) {
      for (posJ <- (posI + 1) until a.size) {
        val tupleI = (posI - a(posI.toInt), posI + a(posI.toInt))
        val tupleJ = (posJ - a(posJ.toInt), posJ + a(posJ.toInt))
        if ((tupleI._1 >= tupleJ._1 && tupleI._1 <= tupleJ._2) ||
          (tupleI._2 >= tupleJ._1 && tupleI._2 <= tupleJ._2) ||
          (tupleI._1 <= tupleJ._1 && tupleI._2 >= tupleJ._2)) {
          count += 1
        }
      }
    }
    count.toInt
  }
}

You will get 100/100 for the below solution in Java language

if (A == null || A.length < 2) {
  return 0;
}

int[] B = Arrays.copyOf(A, A.length);
Arrays.sort(B);
int biggest = B[A.length - 1];
int intersections = 0;
for (int i = 0; i < A.length; i++) {
  for (int j = i + 1; j < A.length; j++) {
    if (j - biggest > i + A[i]) {
      break;
    }
    if (j - A[j] <= i + A[i]) {
      intersections++;
    }
    if (intersections > 10000000) {
      return -1;
    }
  }
}

return intersections;

JavaScript 2016

JavaScript version of Aryabhattas. I've changed it a bit making it more JS and more efficient performance wise and also added comments to explain what the algorithm does. Hope this helps.

function solution(A) {
  var result = 0,
    len = A.length,
    dps = new Array(len).fill(0),
    dpe = new Array(len).fill(0),
    i,
    active = len - 1,
    s,
    e;

  for (i = 0; i < len; i++) {

    // adds to the begin array how many discs begin at the specific position given
    if (i > A[i])
      s = i - A[i];
    else
      s = 0;

    // adds to the end array the amount of discs that end at this specific position
    if (active - i > A[i])
      e = i + A[i]
    else
      e = active;

    // a disc always begins and ends somewhere, s and e are the starting and ending positions where this specific disc for the element in A at position i reside
    dps[s] += 1;
    dpe[e] += 1;
  }

  // no discs are active as the algorithm must calculate the overlaps first, then the discs can be made active, hence why it begins with 0 active
  active = 0;
  for (i = 0; i < len; i++) {
    if (dps[i] > 0) {
      // new discs has entered the zone, multiply it with the current active discs as the new discs now overlap with the older active ones
      result += active * dps[i];
      // new discs must also be counted against each other and not just the ones which were active prior
      result += dps[i] * (dps[i] - 1) / 2;
      // assignment rules
      if (10000000 < result)
        return -1;
      // add new discs to the active list that have started at this position
      active += dps[i];
    }
    // remove discs as they have ended at this position
    active -= dpe[i];
  }
  // return the result
  return result;
}

var A = [1, 5, 2, 1, 4, 0]; // should return 11
console.log(solution(A));