Counting Disk Intersections using TreeSet

Question

I'm trying a demo problem of Codility, before I take the real test as part of a job application. One of the demos they have is a problem involving counting the number of disk intersections, for an array of disks.

Task description is

Given an array A of N integers, we draw N discs in a 2D plane such that the I-th disc is centered on (0,I) and has a radius of A[I]. We say that the J-th disc and K-th disc intersect if J ≠ K and J-th and K-th discs have at least one common point. Write a function: class Solution { public int number_of_disc_intersections(int[] A); } that, given an array A describing N discs as explained above, returns the number of pairs of intersecting discs.

You can view the test here.

There are somewhat obvious O(n^2) time complexity solutions, but the aim is for O(n*log(n)).

I've come up with this, which works on any examples I've provided, and the simple test case given by codility ( [1, 5, 2, 1, 4, 0] ), but Codility tells me it fails on most others but I can't quite see why.

It should certainly be O(n log n) as adding each of n disks to a TreeSet is log n, and then we walk through each disks, with only the O(1) operation TreeSet.headSet().

import java.util.*;

class Circle implements Comparable<Circle> {
  long edge;
  int index;

  Circle (long e, int i){
    edge = e;
    index = i;
  }

  long getRightAssumingEdgeIsLeft(){
    return (long)(2*index - edge + 1);
  }

  @Override
  public int compareTo(Circle other){
    return Long.valueOf(edge).compareTo(other.edge);
  }
}

class Solution {
  public int number_of_disc_intersections ( int[] A ) {
    int N = A.length;
    if (N<2) return 0;
    int result = 0;

    SortedSet<Circle> leftEdges  = new TreeSet<Circle>();
    for (int i=0; i<N; i++) {
      leftEdges.add( new Circle( (long)(i-A[i]), i ) );
    }
    int counter = 0;
    for (Circle c : leftEdges) {
      long rightEdge = c.getRightAssumingEdgeIsLeft();
      Circle dummyCircle = new Circle (rightEdge, -1);
      SortedSet<Circle> head = leftEdges.headSet(dummyCircle);
      result +=  head.size() - counter;
      if (result > 10000000) return -1;
      counter++;
    }
    return result;
  }
}

Answer 1

There is a simpler way...

1. Create 2 arrays of N elements (leftEdge, rightEdge).
2. For each element calculate left and right edge (index -/+ value) and set it in arrays.
3. Sort arrays.
4. For each element in rightEdge array loop through leftEdge array to find first greater or equal element. Save number of remaining elements and current index. For next element start loop from saved index...

This way we really loop through each sorted array only once, so algorithm's complexity is O(N log N).

Answer 2

First thing: you defined compareTo() but not equals(). TreeSet JavaDoc says: "the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals"

Other oddity: I don't understand what is the edge field, nor why you set it to i - A[i].