Codility ‘NumberOfDiscIntersections’ 2010 Beta Solution

Short Problem Definition:

Compute intersections between sequence of discs.

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.

Link

Number of Disc Intersections

Complexity:

expected worst-case time complexity is O(N*log(N))

expected worst-case space complexity is O(N)

Execution:

In my mind this problem is very similar to the Codility Fish. You keep count of how many not-yet-ended disks there are. Every beginning has to cross all not-yet-ended disks. The best explanation on the web was written by Luca. His solution is much better than my C-style double-checked while loop. I therefore created a mixture of both 🙂

  • Keep in mind that any pair of circles can intersect only once.
  • If 1+ beginnings have the same point as 1+ endings. You first have to process the beginnings. The old and new ones have per definition a meeting point.
Solution:
def solution(A):
    circle_endpoints = []
    for i, a in enumerate(A):
        circle_endpoints += [(i-a, True), (i+a, False)]

    circle_endpoints.sort(key=lambda x: (x[0], not x[1]))

    intersections, active_circles = 0, 0

    for _, is_beginning in circle_endpoints:
        if is_beginning:
            intersections += active_circles
            active_circles += 1
        else:
            active_circles -= 1
        if intersections > 10E6:
            return -1

    return intersections

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • João Prudêncio

    Isn’t the time complexity here nlogn + n ?
    Since nlogn is for sorting an you also iterate through all the array.

  • BruceFromSeattle

    I submit 2 solutions (in C#, sorry) which are 100% in agreement and 100% Codility correct; 2nd one is 100% Codility performant.

    static int solution(int[] A) // time O(N^2), space O(1)
    { // simple-minded way: check if each (unordered) pair is intersecting
    int n = A.Length;
    int numIntersecs = 0;
    for (long i = 0; i < n – 1; i++)
    for (long j = i + 1; j < n; j++)
    if (i – A[i] <= j + A[j] && j – A[j] <= i + A[i]) //just touching is intersection
    if (numIntersecs == 10E6)
    return -1;
    else
    numIntersecs++;
    return numIntersecs;
    }
    static int solution(int[] A) // time O(N*Log(N)), space O(N)
    { // decrement max number of pairs by number of non-intersecting pairs
    long n = A.Length;
    if (n < 2)
    return 0;
    long numIntersecs = n * (n – 1) / 2; // unordered pairs, initialized to max possible
    long[] hiVals = new long[n];
    long[] loVals = new long[n];
    for (long i = 0; i < n; i++)
    {
    hiVals[i] = i + A[i]; // high value of disk edge (along x-axis)
    loVals[i] = i – A[i]; // low value of disk edge (along x-axis)
    }
    Array.Sort(hiVals);
    Array.Sort(loVals);
    int jLo = 0; // initialize inner iterator only once
    for (int iHi = 0; iHi < n; iHi++)
    {
    for ( ; jLo hiVals[iHi]) // disks don’t intersect if one’s lo > other’s hi
    {
    numIntersecs -= n – jLo; // decrement by the num of lo values > this hi value
    break; // don’t increment iterator, check this low value again next time
    }
    }
    if (jLo == n)
    break; // no more low values > high values
    }
    if (numIntersecs > 10E6)
    return -1;
    else
    return (int) numIntersecs;
    }

  • Pias Kumar Das

    Here is my solution.(100/100)

    public int solution(int[] A) {
    // write your code in Java SE 8
    // write your code in Java SE 8
    if(A.length<2)
    return 0;
    Long r[]=new Long[A.length];
    Long l[]=new Long[A.length];

    for(int i=0;i<A.length;i++)
    {
    if(A[i]==0)
    {
    r[i]=l[i]=(long)i;
    }
    else
    {
    r[i]=(long)i+A[i];
    l[i]=(long)i-A[i];
    }
    }

    Arrays.sort(r);
    Arrays.sort(l);

    int in=0;
    long s=0;

    for(int i=0;ir[in])
    {
    int y=0;
    while(inr[in])
    {
    y++;
    in++;
    }
    if(y>0)
    s=s+(l.length-i)*y;
    }

    }

    long t=(((long)A.length)*((long)A.length-1))/2;
    //System.out.println(t-s);
    if((t-s)>10000000)
    return -1;
    return (int)(t-s);
    }

  • Pias Kumar Das

    my solution:(100/100)

    public int solution(int[] A) {
    // write your code in Java SE 8
    // write your code in Java SE 8
    if(A.length<2)
    return 0;
    Long r[]=new Long[A.length];
    Long l[]=new Long[A.length];

    for(int i=0;i<A.length;i++)
    {
    if(A[i]==0)
    {
    r[i]=l[i]=(long)i;
    }
    else
    {
    r[i]=(long)i+A[i];
    l[i]=(long)i-A[i];
    }
    }

    Arrays.sort(r);
    Arrays.sort(l);

    int in=0;
    long s=0;

    for(int i=0;ir[in])
    {
    int y=0;
    while(inr[in])
    {
    y++;
    in++;
    }
    if(y>0)
    s=s+(l.length-i)*y;
    }

    }

    long t=(((long)A.length)*((long)A.length-1))/2;
    //System.out.println(t-s);
    if((t-s)>10000000)
    return -1;
    return (int)(t-s);
    }

    • seems that I managed to fix it…

      – besides you also need the block.
      - the after adding pre, the code coloring kicked in, but it was still messed up. It seems that you need to have a space in between any text and your code block. I did not know that. The code probably needs it's own paragraph...


  • public int solution(int[] A) {
    // write your code in Java SE 8
    // write your code in Java SE 8
    if (A.length < 2)
    return 0;
    Long r[] = new Long[A.length];
    Long l[] = new Long[A.length];

    for (int i = 0; i < A.length; i++) {
    if (A[i] == 0) {
    r[i] = l[i] = (long) i;
    } else {
    r[i] = (long) i + A[i];
    l[i] = (long) i - A[i];
    }
    }

    Arrays.sort(r);
    Arrays.sort(l);

    int in = 0;
    long s = 0;

    for (int i = 0; i r[in]) {
    int y = 0;
    while (in r[in]) {
    y++;
    in++;
    }
    if (y > 0)
    s = s + (l.length - i) * y;
    }

    }

    long t = (((long) A.length) * ((long) A.length - 1)) / 2;
    //System.out.println(t-s);
    if ((t - s) > 10000000)
    return -1;
    return (int) (t - s);
    }

  • Eduardo

    I don’t fully understand codility lesson… For the example (counting duplicates)
    Discs that intersect
    0 with (1,2,4)
    1 with (0,2,3,4,5)
    2 with (0,1,3,4)
    3 with (1,2,4)
    4 with (0,1,2,3,5)
    5 with (1,4)
    Pairs of discs that intersect (output 11 without duplicates)
    (0,1), (0,2), (0,4)
    (1,2), (1,3), (1,4), (1,5)
    (2,3), (2,4)
    (3,4)
    (4,5)

    But my code failed for input array[1,1,1], codility says that output should be 3 but I only can see 2 following above logic of deleting duplicates
    Discs that intersect
    0 with (1)
    1 with (0,2)
    2 with (1)
    Pairs of discs that intersect (output 2 without duplicates) > Codility expects 3!
    (1,0), (1,2)

    Can you give a clue about what I am understanding wrong? Thanks!