Last Updated: 27 Mar, 2022
Colourful Balls
Moderate
Asked in company
There are 'N' balls arranged in a row from left to right. Each of the balls has a colour that can be represented by a number between 1 and 10^9.
For each 'i' = 0, 1, 2.. 'N-1', the colour of the 'i-th' ball from the left is Colour 'Ai'.
Ninja can choose 'K' consecutive balls from this row. That is, he can choose an integer 'i' such that 0 <= i <= 'N - K' and get the balls 'i', 'i+1', 'i+2' … '(i+k-1)' from the left. Additionally, he can choose at most one of those 'K' balls and repaint it to a colour of his choice.
Ninja wants to get the maximum variety in colours in the selected 'K' consecutive balls, and for this, he will choose some optimal 'i'. Return the maximum possible number of distinct colours in balls he can get.
Example :
‘N’ = '6'
'K' = '3'
The next line contains 'Ai', the colour of the 'ith' ball from the left,
1 2 1 3 2 3
Assuming 0-based indexing, If Ninja gets the balls from index 2 to 4, i.e., the contiguous set {1,3,2} he will have 3 different coloured balls, which is the maximum possible answer.
He can also get the balls from index 1 to 3, i.e., the set {2,1,3}.
Input Format :
The first line contains an integer 'T', which denotes the number of test cases to be run. Then the test cases follow.
The first line of each test case contains two space-separated integers, ' N' and 'K', denoting the total number of balls and the number of balls Ninja can take, respectively.
The second line of each test case contains 'N' space-separated integers 'Ai', where the 'ith' element denotes the colour of the ball 'i'.
Output format :
For each test case, return the maximum possible number of distinct colours in balls Ninja can pick.
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 <= K <= N <= 10^5
1 <= Ai <= 10^9 (0 <= i <= N-1)
The sum of 'N' overall 'T' does not exceed 10^5.
Time Limit: 1 sec
Approaches
Approach :
- There are 'N' possible ways to choose starting levels. We will try all possible starting levels.
- For each starting level,
- We insert the next 'K' elements in a set.
- When we are done with picking 'K' elements, we check the number of unique elements in our set.
- If the unique elements do not equal 'K', there exists at least one duplicate colour which can be painted to an arbitrary different colour.
- Based on the unique elements in every iteration, store the answer.
- Lastly, return the answer.
Algorithm:
- Initialize an integer variable 'ans' = 0.
- Iterate through elements of 'A',
- Initialize an associative array (or any data structure that stores unique elements).
- If the current index 'i' is greater than 'N-K', break since we can't pick 'K' balls.
- In another loop with variable 'j', iterate through the elements of 'A' from index 'i' to 'i+K', and insert elements into the set.
- If the set size is less than 'K', update 'ans' as max of (ans, size of set + 1); otherwise, update 'ans' as max of (ans, size of set).
- Return 'ans' as the final output.
Approach :
- Assume that we have just inspected [i,i+K−1] and now want to inspect [i+1,i+K] right after that.
- Here, note that adding the (i+K)-th ball to the window under inspection, and then removing the i-th ball from [i,i+K−1], results in [i+1,i+K].
- So, when inspecting [i+1,i+K], instead of inspecting all the candies in [i+1,i+K], we can only focus on the "difference" between the [i,i+K−1] that just have been checked.
- This can be done by decreasing the frequency of the 'i-th' ball from the container ( like set) and erasing the ball if the frequency drops to 0.
- In each window of size 'K', we update our Answer based on the unique elements in the window.
Algorithm:
- Initialize an integer variable 'res' = 0, a pointer 'i' as '0 and a pointer 'j' as '0'.
- Initialize an associative array, like a hashmap.
- With 'i' as the first pointer and 'j' as the second pointer, move as follows:
- While 'j' < 'N' and '( j-i+1)' <= 'K'
- Increment the frequency of 'A[j]' in the hashmap.
- Increment 'j' by 1.
- Initialize an integer variable 'current' as the size of the hashmap.
- If the hashmap size does not equal K, increment 'current' by 1.
- Update' res' as the max of 'res' and 'current'.
- Decrease the frequency of 'A[i]' in the hashmap. If the value of 'A[i]' value n the hashmap becomes 0, delete the key 'A[i]' from the hashmap.
- Increment' i' by 1.
- While 'j' < 'N' and '( j-i+1)' <= 'K'
- Return 'res' as the final output.