📄 Problem Description 🤔

The managers of Gardaland Theme Park are building a new attraction, consisting of a sequence of N chambers of horrors, each located at a different height of H[i]​ meters. Together with the attraction, they also plan to build a scenic walkway following most of the chambers from the outside.

In order to maximise the visibility of the new attraction, they need to carefully plan the altitude at which to build the walkway. For this reason they hired Giorgio, who calculated that it would be best if at least K chambers were clearly visible from the walkway. Given a set of chambers, define its spread as the difference between the highest and the lowest chamber in the set. Find the smallest possible spread for a set of K chambers!

Input:

The first line contains the two integers N and K. The second line contains N integers H[i]​.

Output:

You need to write a single line with an integer: the smallest possible spread for a set of K chambers.

Constraints:

• 2 ≤ K ≤ N ≤ 1,000,000

• 0 ≤ H[i] ≤ 1,000,000 for each i=0…N-1

Sample testcases:

Explanation of sample testcases:

👇 Here is the Solution! 💡

An obvious solution would be to try all the possible sets of K elements. We will see that this solution is actually incredibly slow, and it also proves quite difficult to implement in languages such as C++ (in Python it's quite easy because of its rich standard library, see: itertools.combinations).

As it usually happens, “obvious” solutions are often wrong (or too slow). In fact, here the number of possible combinations of K elements from a set of N elements can become huge. In the example above, with N=10 and K=3, we only have 120 possible combinations. If we increased to N=30 and K=15 we would have more than 150 million combinations! Solving such a testcase is probably still feasible within the time limit, but what's the worst possible testcase?

From the “Constraints” section of the problem description (and from a quick look at Pascal's triangle) we can see that the worst possible case is when N=1000000 and K=500000. In that case, the number of combinations will be around 10³⁰¹⁰²⁶, yes, that number is “1” followed by 301026 zeroes!

For perspective, the observable universe is estimated to “only” have around 10⁸⁰ atoms.

Let's do it faster

Let's take the example with N=10 and the following heights (the solution, with spread 6, is marked):

67, 90, 22, 79, 95, 89, 76, 21, 65, 99

Let's sort the heights in increasing order (but we will see that also decreasing order is OK):

21, 22, 65, 67, 76, 79, 89, 90, 95, 99

Now that the numbers are sorted, we can easily see that it's never a good idea to choose K chambers which are not consecutive in the sorted array. Why is that? Well, because if we chose a non-consecutive set then it would obviously be possible to reduce its spread by replacing some chamber!

This leads us to a much faster solution: just sort the numbers and then test all the (N-K+1) possible “windows” of K consecutive elements.

C++ Solution

#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

int main() {

    int N, K;

    cin >> N >> K;

    vector<int> v(N);

    for (int i = 0; i < N; ++i) {

        cin >> v[i];

    }

    sort(v.begin(), v.end());

    int best = 1000000000;

    for (int i = 0; i < N - K + 1; ++i) {

        best = min(best, v[i + K - 1] - v[i]);

    }

    cout << best << endl;

}

In our tests, this solution runs in just under 0.5 seconds (and uses 5 MiB of RAM) on the hardest testcases we have.

Python3 Solution

N, K = map(int, input().split())

v = list(map(int, input().split()))

v.sort()

best = 10**9

for i in range(N - K + 1):

    best = min(best, v[i + K - 1] - v[i])

print(best)

In our tests, this solution runs in just under 2 seconds (and uses 118 MiB of RAM) on the hardest testcases we have.

Java Solution

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.Arrays;

import java.util.StringTokenizer;

public class Main  // class name should be "Main"

{

    public static void main(String[] args) throws IOException

    {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st;

        // Read line #1

        st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());

        int K = Integer.parseInt(st.nextToken());

        // Read line #2

        st = new StringTokenizer(br.readLine());

        int[] v = new int[N];

        for (int i = 0; i < N; i++) {

            v[i] = Integer.parseInt(st.nextToken());

        }

        Arrays.sort(v);

        int best = 1000000000;

        for (int i = 0; i < N - K + 1; i++) {

            best = Math.min(best, v[i + K - 1] - v[i]);

        }

        System.out.println(best);

    }

}

In our tests, this solution runs in about 1.5 seconds (and uses 104 MiB of RAM) on the hardest testcases we have.