Minimum Value

Easy
0/40
Average time to solve is 15m
19 upvotes
Asked in company
Amazon

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1 
5 2
1 3 5 4 4
Sample Output 1 :
0
Explanation of sample input 1:
For the array {1, 3, 5, 4, 4}, all the unique subsets of K size are (1, 3), (1, 5), (1, 4), (3, 5), (3, 4), (5, 4), (4, 4). 
The minimum value of the difference between the maximum and the minimum of any subset is 0. Thus, 0 is the answer.
Sample Input 2 :
2
10 3 
4 5 2 9 8 1 1 7 10 3
7 7 
7 5 3 2 1 6 6
Sample Output 2 :
1
6
Explanation of sample input 2:
Test case 1: 
If we consider the subset { 2, 1, 1 }, we will get the minimum required value.

Test case 2: 
The value of K is equal to N. Thus; we have to consider the complete array as the subset.
Hint

Can you think about generating all the subsets of size ‘K’?

Approaches (2)
Recursion

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: 

 

  1. 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.
  2. 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’.

Time Complexity

O((NcK) * K ), Where N is the number of elements in the given array/list, and ‘K’ is the size of subsets, and NcK is the number of ways of selecting K numbers from N numbers.

 

Since we are selecting K numbers from N numbers, and then traversing all the subsets of K numbers, the total time complexity becomes O((NcK) * K ).

Space Complexity

O(N + K), Where N is the number of elements in the given array/list, and ‘K’ is the size of subsets.

 

In the worst case, the recursion stack space used is O(N). Also, we are storing at most ‘K’ elements at a time. Thus, the final complexity will become O(N + K).

Code Solution
(100% EXP penalty)
Minimum Value
Full screen
Console