Last K Sized Group

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
0 upvote
Asked in companies
SAP LabsNextechFlipkart limited

Problem statement

You are given an array/list ‘ARR’ containing permutation from 1 to 'N' and an integer ‘K’. You have a binary string ‘S’ of size ‘N’ initialised to all zeroes. You perform ‘N’ operations on 'S' as follows:

In the ‘i-th’ operation, you set the ‘ARR[i]-th’ bit of ‘S’ to ‘1’.

After performing each operation, you get a "group". A "group" of '1s', is a substring of all '1s' in 'S' which can not be extended to its left or right by adding '1s'.

You have to find the last operation when there was a group of size exactly 'K'. If the group of size 'K' was never present, then return -1.

Note :

Both 'ARR' and 'S' are 1 indexed.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain two space-separated integers, ‘N’ and 'K', which denotes the length of the permutation 'ARR', and the required size of the group, respectively. 

The second line of each test case will contain 'N' single space-separated integers, representing the permutation 'ARR'.
Output Format : 
For each test case, print the last operation when there was a group of size 'K', else print -1. 

Output for every test case will be printed in a separate line.
Note : 
You don’t need to print anything; It has already been taken care of.
Constraints : 
1 <= T <= 10
1 <= N <= 100000
1<= K <=N
1<= ARR[i] <= N


Where ‘T’ is the number of test cases, 'N' is the size of the permutation, 'K' is the size of the required group, and 'ARR[i]' is an element of the permutation.

Time limit: 1 sec
Sample Input 1 :
2
3 1
1 3 2
4 3
2 1 4 3
Sample Output 1 :
2
-1
Explanation of sample input 1 :
In the first test case :
After 1st operation, 'S' = "100". There is 1 group of size 1 from [1,1].
After 2nd operation, 'S' = ''101". There are 2 groups of size 1 from [1,1] and [3,3].
After 3rd operation, 'S' = "111". There is one group of size 3 from [1,3].
A group of size 1 was last present after the second move. 

In the second test case :
After 1st operation, 'S' = "0100". There is 1 group of size 1 from [2,2].
After 2nd operation, 'S' = "1100". There is 1 groups of size 2 from [1,2]. 
After 3rd operation, 'S' = "1101". There is 1 group of size 2 from [1,2] and 1 of size 1 from [4,4].
After 4th operation, 'S' = "1111". There is one group of size 4 from [1,4].
Group of size 3 was never present.
Sample Input 2 :
2
1 1
1
7 7
1 2 3 4 5 6 7
Sample Output 2 :
1
7
Hint

Can we perform all the operations and merge two adjacent groups and create a bigger group?

Approaches (1)
Simulation

We will go through all the operations and check which old groups will merge and which new groups will get created. 

 

We will maintain two arrays, 'left' and 'right' to store the length of groups of '1s' ending at 'i' and starting at 'i'. 

 

To get the last index when there was a group of size 'K', we will check whether the newly merged group had size 'K'.

 

The steps are as follows:

 

  1. If 'K' is equal to 'N':
    1. It is only possible after all the operations are performed.
    2. Return 'N'.
  2. Create a variable 'ans' initialize to -1 to store the final answer.
  3. Create an array 'left' of size 'N+2', left[i] is the length of group ending at 'i'.
  4. Create an array 'right' of size 'N+2', right[i] is the length of the group starting at i.
  5. Iterate from 0 to ‘N’-1. (say, iterator = 'i'):
    1. 'leftLength' = 'left[arr[i]-1]'
    2. 'rightLength' = 'right[arr[i]+1]'
    3. After 'arr[i]' bit gets set in 'S', 'leftLength' and 'rightLength' will merge. If any of the lengths equal to 'K'.
      1. 'ans' = 'i'
    4. A new group of length 'leftLength' + 'rightLength' + 1 will be created.
    5. 'left[arr[i]+right]' = 'leftLength' + 'rightLength' + 1
    6. 'right[arr[i]-left]' = 'leftLength' + 'rightLength' + 1
  6. Return 'ans'.
Time Complexity

O(N), where ‘N’ is the length of the permutation.

 

We will do each operation once so, the overall time complexity will be O(N).

Space Complexity

O(N), where ‘N’ is the length of the permutation.

 

Since the space required by 'left' and 'right' array is O(N) so, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Last K Sized Group
Full screen
Console