Horse-racing Duals – CodinGame solution in C
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
- 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.
- Sort ascendingUse the standard library sort (qsort, Arrays.sort, sorted, sort -n). After sorting, equal or close values sit next to each other.
- 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.
- 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
O(N log N)O(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;
}
Horse-racing Duals – Java
import java.util.*;
import java.io.*;
class Solution {
public static void main(String args[]) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine().trim());
int[] power = new int[n];
for (int i = 0; i < n; i++)
power[i] = Integer.parseInt(in.readLine().trim());
// after sorting, the closest pair is always made of two neighbours
Arrays.sort(power);
int best = Integer.MAX_VALUE;
for (int i = 1; i < n; i++)
best = Math.min(best, power[i] - power[i - 1]);
System.out.println(best);
}
}
Horse-racing Duals – Python 3
Keeps the list sorted while reading with bisect.insort, then scans adjacent pairs. Each insertion shifts elements, so this is O(N^2) in theory, but the shift is a fast memmove and it still runs well under a second for 100,000 values.
import bisect, sys
N = int(input())
horses = []
mini, diff = sys.maxsize, None
for i in range(N):
bisect.insort(horses, int(input()))
for i in range(N-1):
diff = horses[i+1] - horses[i]
if diff < mini:
mini = diff
print(mini)
Horse-racing Duals – Bash
Pipes the values through sort -n to sort the array, then loops over neighbours with arithmetic expansion; slow-ish but within limits.
#!/bin/bash
read N
# reads all power values and store them in an array
for (( i=0; i<N; i++ ))
do
read p
power[$i]=$p
done
# sorts the array
power=($(for p in ${power[@]}; do echo $p; done | sort -n))
# at this point, power contains all the power sorted by increading order
# the result expected is the smallest difference between 2 consecutive values
min=9999999
for (( i=0; i<${#power[@]}-1; i++ ))
do
current=${power[$i]}
next=${power[$i+1]}
diff=$(( next - current))
if [ $diff -lt $min ]
then
min=$diff
fi
done
echo $min
Common mistakes
- Double loop over all pairsChecking every pair is about 5 billion comparisons for N = 100,000. It passes the first tests and fails the last one with a timeout.
- Using a set and losing duplicatesA TreeSet, HashSet or Python set removes equal strengths, but two equal horses are exactly the case where the answer is 0. If you insert into a set, treat a failed insertion as an immediate answer of 0.
- Starting the minimum too lowInitialising the minimum to a guess like 1,000,000 breaks when the only two horses are far apart. Start from INT_MAX, infinity, or the first difference.
- Sorting as stringsIn JavaScript, Array.prototype.sort() without a comparator sorts lexicographically, so 10 comes before 9. Use sort((a, b) => a - b), and in Bash use sort -n, not plain sort.
- Slow input in JavaScanner on 100,000 lines is noticeably slow. It usually still passes, but BufferedReader with Integer.parseInt removes any risk.
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.