In this article I will provide a solution to the Intersecting Discs sample Codility problem. The problem description is copyrighted, so have a look at the link for the description. The gist of it is as follows:

Given an array \(A\) of non-negative integers, \(A[i]\) corresponds to the radius of a disc located at \((0,i)\) on the Cartesian plane. Two discs are said to intersect iff they have at least one common point. Compute the total number of intersecting pairs of discs.

1 Attempt 1 - Brute Force

Let’s first try to come up with a brute force solution – this is always a good start.

Given array indices \(i\),\(j\) (\(j > i\)), if the discs are located at \((0,i)\) and \((0,j)\) respectively, then the discs will intersect iff the following holds:

\[ j-i \leq A[i] + A[j] \]

Given this predicate, simply iterate over array \(A\), and check for how many subsequent discs the above predicate holds. This gives us an \(O(n^2)\) algorithm.

2 Improving to \(O(N\operatorname{log}N)\)

We can rewrite the above predicate:

\[ j-i \leq A[i] + A[j] \\ A[i] + i \geq -(A[j] - j) \]

Now we are getting closer to a solution. We see that the solution is dependent on a \(\geq\) predicate where each side is a linear transformation of the input array \(A\). We can proceed as follows:

1. Produce two arrays containing \(A[i] + i\) and \(-(A[j]-j)\).
2. Sort them - \(O(N\operatorname{log}(N))\)
3. Compute for how many pairs the above predicate holds.

To do the last step above, simply go through array with sorted values \(A[i]+i\), and for each value \(x\), check how many values from the sorted array \(-(A[j]-j)\) are smaller than \(x\). This can be done with binary search in \(O(\operatorname{log}(N))\).

Crucially, we must subtract what was counted twice and any degenerate solutions – these where the predicate \(j-i \leq A[i] + A[j]\) holds true since \(j-i \leq 0\). To do this, subtract \(\frac{N*(N+1)}{2}\) from the total.

This leads to the following Java algorithm, which scores 100/100 on Codility:

 public static int intersectingDiscs(int[] A){
    int l = A.length;

    long[] A1 = new long[l];
    long[] A2 = new long[l];
    
    for(int i = 0; i < l; i++){
      A1[i] = (long)A[i] + i;
      A2[i] = -((long)A[i]-i);
    }
    
    Arrays.sort(A1);
    Arrays.sort(A2);
    
    long cnt = 0;
    
    for(int i = A.length - 1; i >= 0; i--){
      int pos = Arrays.binarySearch(A2, A1[i]);
      if(pos >= 0){
        while(pos < A.length && A2[pos] == A1[i]){
          pos++;
        }
        cnt += pos;
      } else{ // element not there
        int insertionPoint = -(pos+1);
        cnt += insertionPoint;
      }
      
    }
    
    long sub = (long)l*((long)l+1)/2;
    cnt = cnt - sub;
              
    if(cnt > 1e7) return -1;
    
    return (int)cnt;
  }

3 Addendum

I got the general idea of the algorithm on my first try, but alas, I scored 35/100. All the errors were stemming from overflow of the int datatype. It took me a couple of tries going up to 50,75, and 93 points out of 100 before finally getting across all of Codility’s tests. This leads to show just how easy it is to screw when working with bounded integer representations. If people do make these overflow mistakes on a programming challenge, then it is only fair to extrapolate that many overflow-related bugs are hiding deep down in some code that make takes user input or fetches data from a database.

While having bounded integers and working with Java puts you much closer to the bare hardware, I’ve come to appreciate the unbounded nature of the Int datatype in Haskell. As a programmer, you already many things to keep track of and make sure your code works well (using the right algorithm for example), and it would seem unnatural to expect of you to remember that adding two natural numbers coming from a database might not result in a natural number depending on how you code it. Or, should I really need to remember what happens when I multiply a long with an int, or if the l-value is a long, but the r-value is composed of ints?

I see a lot of programming simply as definining transformations on data¹, and as a programmer, you shouldn’t have this fear that positive integers are not closed under addition. Having been learning and coding in Haskell for the past few weeks, this is just one of the things I’ve come to appreciate.