Colourful Balls

Moderate
0/80
profile
Contributed by
2 upvotes
Asked in company
Visa

Problem statement

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}.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4 3
1 1 2 1
3 2
2 3 4
Sample Output 1 :
3
2
Explanation Of Sample Input 1 :
For test case 1:
Ninja can choose the balls starting from index 1 to index 3 (0-based indexing), i.e. the set {1,2,1} and repaint the last ball to colour '3' and obtain a set of balls {1,2,3} with 3 distinct colours, Hence we return 3.


For test case 2:
Since all balls are of different colours, Ninja can choose any 2 consecutive balls and get 2 distinct colours which is the answer.
Sample Input 2 :
2
3 3
2 2 3
5 5
1 2 1 1 1
Sample Output 2 :
3
3
Hint

How to find the answer for each index?

Approaches (2)
Brute Force

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.
Time Complexity

O(N*K)

Since for every element 'Ai', we traverse towards the right for 'K' elements

The time complexity of the algorithm is O (N*K) where 'N' is the number of balls and 'K' is the number of consecutive balls that Ninja has to pick.

Space Complexity

O(N)

Since we will be storing elements in an associative array like a set or a map, the Space Complexity is O(N).

Code Solution
(100% EXP penalty)
Colourful Balls
Full screen
Console