Algorithm to calculate number of intersecting discs

Question

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.

Answer 1

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; }