Number of disc intersections - O(N*M) solution

This Codility problem, and a first inefficient solution, is described in the previous post. In few words, we have a vector of elements, each of them is representing a segment on the x axis, we want to calculate how many intersections all these segments have among them. Looping on all the elements, and comparing each one to the others is a shiny Big Oh N Square algorithm, that would lead us to horrible performances as the size of the input grows.

Here I try to make that naive solution more acceptable, tweaking a few algorithm details. In some circumstances, this could even lead to an O(N log N) solution that would make anyone happy. Still, the worst case has again a dismaying O(N square) time complexity.

Some considerations

There's no need to check values on the left of the first disc center (i.e.: zero) and on the right of the last one. We can simply cut the trespassing extremes to match that limits, no information is lost.

If we sort the discs, so that the first is the one "more to the left", and the last is "more to the right", we can simplify the comparison among the current one and its next ones, stopping when we find the first non-intersecting couple.

To sort the discs, we should use a buffer container so that we can use the STL sort() function. I am going to use a raw array of std::pair's, where first is the left limit of a disc and second the right one. Notice that the standard states that the default way an interval of pair's is ordered is just what we need.

Refactoring the code

int beta(const std::vector<int>& input)
{
  const SIZE_T SIZE = input.size(); // 1

  if(SIZE < 2)
    return 0;
  if(SIZE > MAX_ELEMENTS)
    return -1;

  std::pair<nt, int> disks[SIZE]; // 2
  for(SIZE_T i = 0; i < SIZE; ++i)
  {
    disks[i].first = i - input[i] < 0 ? 0 : i - input[i]; // 3
    disks[i].second = (int64_t)input[i] + i >= input.size() ? input.size() - 1 : input[i] + i; // 4
  }

  std::sort(disks, disks + SIZE);

  int result = 0;
  for(SIZE_T i = 0; i < SIZE - 1; ++i) // 5
  {
    for(SIZE_T j = i + 1; j < SIZE; ++j) // 6
    {
      if(disks[i].second >= disks[j].first)
      {
        if(result == MAX_INTERSECTING_PAIRS)
          return -1;
        ++result;
      }
      else // 7
      {
        break;
      }
    }
  }
  return result;
}

1. In theory, any C++ compiler should be aggressive enough to optimize off a call to size(), but I got the impression the Codility compiler isn't. And this algorithm is very sensitive, losing a few millis here and there could be fatal.
2. Prepare to put the discs in this raw array, so that we can sort them.
3. Any first represents the left limit of a disc. As said above, we cut it to zero.
4. Beware of overflow. A value could be (close to) INT_MAX, so increasing it requires a 64 bit integer.
5. Looping on all the discs (but the last one).
6. Looping on all the next discs but ...
7. ... we are dealing with an ordered copy of the original collection of discs, when we see the first one not intersecting, we can stop looping.

Algorithm complexity

The data buffer for sorting costs us an extra O(N) space complexity, but this is allowed by the problem.

The sorting costs O(N log N) in terms of time complexity. In our best case this is the complexity of the algorithm.

Normally we have a O(N*M) time complexity, where M is the average distance between the right limit of any disc to its relative most left one. The best case, happens when there is no intersection at all, and this part of the algorithm becomes less expensive of the sorting. In the worst case, M tends to N/2, so the complexity is again O(N square).

It is easy to write a test case that checks the worst case scenario for this algorithm:

TEST(TestBeta, CaseLastHuge)
{
  std::vector<int> input;
  input.resize(MAX_ELEMENTS); // 1
  input.back() = MAX_VALUE;

  boost::posix_time::ptime start = boost::posix_time::microsec_clock::local_time();

  ASSERT_EQ(MAX_ELEMENTS - 1, beta(input));

  boost::posix_time::time_duration diff = boost::posix_time::microsec_clock::local_time() - start;
  ASSERT_LT(diff.total_milliseconds(), 7); // 2
}

1. We have the biggest possible vector of elements, all of them are zero, but the last one, that it is huge.
2. I'd like the case to be solved in a few millis, but it wouldn't be the case (at least on my machine).

Even if this solution gets a whooping 100/100 on Codility, it is not the best solution that you can achieve. We'll see in the next post a much more elegant and performant algorithm.