Coding Solution

Horse-racing Duals – CodinGame solution in C

Easysortingadjacent differencesgreedyUpdated
Short answer

Read all N strengths into an array, sort it, and scan it once comparing each value with the next one: the smallest of those adjacent differences is the answer. Sorting guarantees that the closest pair are neighbours, so the O(N^2) comparison of every pair is unnecessary and the solution runs in O(N log N), fast enough for 100,000 horses.

The problem

You receive the strength of N horses, one integer per line. You must find two horses whose strengths are as close as possible and print the absolute difference between them.

N can be as large as 100,000 and strengths go up to 10,000,000. Several horses may share the same strength, in which case the answer is 0. The challenge is purely about performance: comparing every pair works on small tests and times out on the big one.

Approach, step by step

  1. Store all strengthsRead the N values into an array. There is no way to answer before the last value is read, because any new horse can create a closer pair.
  2. Sort ascendingUse the standard library sort (qsort, Arrays.sort, sorted, sort -n). After sorting, equal or close values sit next to each other.
  3. Scan adjacent pairsCompute a[i+1] - a[i] for every i and keep the minimum. The difference is never negative because the array is sorted, so no abs() is needed.
  4. Exit early on zero (optional)If a difference of 0 appears, nothing can beat it, so you can stop the loop and print 0 right away.

Complexity

TimeO(N log N)
SpaceO(N)

The sort dominates; the scan after it is linear. Storing the N values is required, since any horse could belong to the closest pair.

Solution code

Bug fixed in this version: The Java version is wrong when two horses have the same strength: a TreeSet silently drops duplicates, so the input 5, 8, 5, 20 prints 3 instead of 0. A replacement that sorts a plain int array (and reads with BufferedReader for speed) is provided. The C, Python and Bash versions handle duplicates correctly.

Horse-racing Duals – C

Reads into a variable-length array on the stack and sorts it with qsort and a three-way comparator; 100,000 ints is only 400 KB, so the stack is fine.

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

/* compares the two integers pointed by e1 and e2, 
   returns -1 / 0 / 1, if e1 < / = / > e2 */ 
int comp (const void * e1, const void * e2) {
    int f = *((int*)e1);
    int s = *((int*)e2);
    if (f > s) return  1;
    if (f < s) return -1;
    return 0;
}

int main(int argc, char** argv)
{
    int N;
    scanf("%d\n", &N);
    int horses[N];
    for (int i = 0; i < N; i++)
        scanf("%d\n", horses+i);

    // Sorts the powers
    qsort(horses, N, sizeof(int), comp);
    
    int min = INT_MAX;
    int diff;
    for (int i = 0; i < N-1; i++) {
        diff = horses[i+1]-horses[i];
        if (diff < min)
                min = diff;
    }

    printf("%d\n", min);
    return EXIT_SUCCESS;
}
            

Common mistakes

Going further

Why is checking neighbours enough? Take the sorted array and any non-adjacent pair a[i] < a[j] with j > i + 1. Then a[j] - a[i] = (a[j] - a[j-1]) + ... + (a[i+1] - a[i]), a sum of non-negative adjacent gaps, so it is at least as large as each of them. The minimum over all pairs is therefore always reached by some adjacent pair. This also tells you that sorting is the bottleneck, not the scan: if strengths were bounded by a small number you could replace the comparison sort by a counting sort or a bitmap and get O(N + max), and in the worst case the problem cannot be done faster than O(N log N) with comparisons, because deciding whether all elements are distinct already requires that much work.

FAQ

Why does my Horse-racing Duals solution time out?

You are almost certainly comparing every pair of horses, which is O(N^2). Sort first and compare only neighbours to get O(N log N).

Can the answer be 0?

Yes. If two horses have the same strength the closest pair has a difference of 0. Data structures that remove duplicates, such as TreeSet or set, hide this case.

Do I need abs() when computing the difference?

Not after sorting in ascending order: a[i+1] - a[i] is always zero or positive. You only need abs() if you compare values in their original order.

Similar puzzles

★ 5.0 · 16 reviews · 928 users Add to Chrome