Carpet and Boxes

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
2 upvotes

Problem statement

You are given 'N' boxes of width 1 unit. You are also given an array 'POSITION' which denotes the positions of the boxes, e.g POSITION[ i ] denotes the position of the ith box. You need to cover any 'K' boxes with a carpet.

Find the minimum length of the carpet to cover any 'K' boxes.

Example: 
Input: ‘N’ = 3, ‘K’ = 2, 'POSITION' = [2, 3, 6] 

Output: 2


 There are two possible ways to cover exactly two boxes. One covers the boxes at positions 2 and 3 and the other at positions 3 and 6. The carpet lengths required for both ways are 2 ( Since boxes are at positions 2 and 3 each having width 1) and 4, respectively. So the minimum length of the carpet is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains two integers ‘N’ and ‘K’ denoting the length of the array 'POSITION' and the number of boxes to be covered respectively.
The second line of each test case contains ‘N’ integers denoting the position of the boxes.
Output format : 
For each test case, return the minimum length of the carpet to cover any ‘K’ boxes.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^5
K > 0
1 <= POSITION[i] <= 10^9

Time Limit: 1 sec
Sample Input 1 :
2
4 3
4 9 2 6
2 1
1 2
Sample Output 1 :
5
1
Explanation Of Sample Input 1 :
For the first case:
There are two possible ways to cover exactly three boxes. One covers the boxes at positions 2, 4 and 6 and the other at positions 4, 6 and 9. The carpet lengths required for both ways are 5 and 6, respectively. So the minimum length of the carpet is 5. 

For the second case:
Since we need to cover only one box, the minimum length of the carpet is 1.
Sample Input 2 :
2
5 2
100 2 95 145 47 
1 1
100
Sample Output 2 :
6
1
Hint

Can you think about some straightforward solution?

Approaches (2)
Brute Force

In the naive approach, since we need to cover exactly ‘K’ boxes, we need to sort the boxes based on their position and then iterate over all the boxes. For the ith box, select ‘K’ consecutive boxes starting from the ith box, then the total length of the carpet required to cover these boxes is given by POSITION[i+K] - POSITION[i] + 1. Iteratively find the minimum of the expression POSITION[i+K] - POSITION[i] +1 for each i.


 

The steps are as follows:-

Function  getMinimumLength(vector<int>&POSITION, int K):

  1. Sort the array in increasing order.
  2. Initialise a variable named ‘MINLEN’ = INT_MAX which will store the minimum length of the carpet required to cover K boxes. Where INT_MAX is some big number which is always greater than ans.
  3. Iterate over all the boxes from 0 to N-K
    • Initialise a variable 'J' = 'I' then keep incrementing it unless (J - I +1)!=K
    • If the difference in position between box at 'I' and box at 'J' is less than ‘MINLEN' then update ‘MINLEN’.
  4. Return the value of the variable ‘MINLEN’.
Time Complexity

O( N * K ), Where N denotes the total number of boxes available and K denotes the number of boxes to be covered by carpet.

 

We first sort the array which takes the time complexity of O( N * Log ( N ) ) then for each box we are iterating over the ‘K’ consecutive boxes. Iterating over ‘K’ consecutive boxes takes the complexity of O( K ) and we are doing it for each box.

Hence the time complexity is O( N * K ).

Space Complexity

O( 1 )

 

We are using no extra space.

Hence space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Carpet and Boxes
Full screen
Console