Last Updated: 8 Jun, 2022
Carpet and Boxes
Moderate
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.
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
Approaches
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):
- Sort the array in increasing order.
- 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.
- 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’.
- Return the value of the variable ‘MINLEN’.
Instead of Iterating over the ‘K’ consecutive boxes. We can use two pointers ‘L’ and ‘R’ in which if ‘L’ is at the box ‘I’ then R will be at the Kth box starting from ‘I’.
The steps are as follows:-
Function getMinimumLength(vector<int>&POSITION, int K)
- Sort the array 'POSITION' in increasing order.
- Initialise two pointers ‘L’ = 0 and ‘R’ = 0.
- 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.
- Loop while ‘R’ < size of the array.
- Loop While ‘R’ < Size of the array and ‘R’ - ‘L’ + 1 is not equal to ‘K’.
- Increment the ‘R’ pointer by 1.
- Update the variable ‘MINLEN’ to a minimum of ‘MINLEN’ and POSITION[R] - POSITION[L] + 1.
- Increment the ‘L’ pointer by 1.
- Loop While ‘R’ < Size of the array and ‘R’ - ‘L’ + 1 is not equal to ‘K’.
- Return the value of the variable ‘MINLEN’.