Last Updated: 10 Dec, 2020

Minimum Value

Easy

Asked in company

Solve now

Problem statement

Given an array/list of size ‘N’ and a positive integer ‘K’. You can pick any subset of ‘K’ numbers from the array/list. The task is to find the minimum possible difference between the maximum and the minimum value in the subset.

For example :

Consider an array of size six. The elements of the array are { 6, 4, 3, 5, 5, 1 }, and the value of ‘K’ is 3. 
If we select {1, 3, 6}, the output will be the difference of the maximum of (1, 3, 6) and the minimum of (1,3, 6), i.e. 5. 
If we select {4, 5, 5}, the output will be the difference of the maximum of (4, 5,  5) and the minimum of (4, 5, 5), i.e. 1.
Among all such possible values, 1 is the minimum, and hence, it is the correct output.

Input Format :

The first line of input contains an integer T, denoting the number of test cases.

The first line of every test case contains two integers ‘N’ and ‘K’ denoting the size of the array/list and the number of elements in the subset, respectively. 

The second line of every test case contains ‘N’ space-separated integers.

Output Format :

For every test case, return the minimum possible difference between the maximum and the minimum value in the subset of size ‘K’. 

The output of each test case is printed in a separate line.

Note :

You don’t have to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 5    
1 <= K <= 100
K <= N <= 100
-10^5 <= ARR[i] <= 10^5

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Recursively generate all the subsets of size ‘K’ and keep track of the minimum possible value of the difference between the maximum and the minimum value in each subset.

Initialize a variable ‘ANS’ by +ve infinity (i.e. INT_MAX), to store the final answer.

Subsets can be generated in the following way. For every element of the array, there are two options:

Include the element in the current subset: If we include the current element in the subset, then we decrease the value of ‘K’ by 1.
Do not include the current element in the current subset: There is no effect on the value of ‘K’, and we can simply move on to the next element.

In any step, if the value of ‘K’ becomes 0, then we have found a subset of size ‘K’. Now traverse the current subset and find the minimum and the maximum value.

Update the ‘ANS’ if the difference between the maximum and the minimum value in the current subset is less than the ‘ANS’.

In the end, ‘ANS’ will contain the minimum difference between the maximum and the minimum value in any subset of length ‘K’. So return the ‘ANS’.

Solve now

02 Approach

How can we minimise the difference between the maximum and the minimum value of any ‘K’ sized subset?

The idea is to sort the given array/list and choose each subset of ‘K’ continuous integers. We can sort the given array/list because while manipulating subset and finding the maximum and minimum value does not depend on the order of elements.

Steps are as follows :

Sort the given array.
Initialise a variable ‘ANS’ by +ve infinity (i.e. INT_MAX), to store the final answer.
Traverse the array from left to right:
1. Consider the K numbers and calculate the maximum(K numbers) – minimum(K numbers) i.e. (ARR[CURR_INDEX + K - 1] - ARR[CURR_INDEX]) and store it in a variable ‘CURRENT_MIN’.
2. Update the ‘ANS’ by ‘CURRENT_MIN’ if ‘CURRENT_MIN’ is less than ‘ANS’.
Return the ‘ANS’.

Solve now