Divide Array In K Sets Of Consecutive Numbers

Moderate
0/80
Average time to solve is 15m
1 upvote
Asked in companies
UberMicrosofteBay

Problem statement

Given an array of integers ‘ARR’ and a positive integer ‘K’, find whether it's possible to divide this array into sets of 'K' consecutive numbers.

Example:

Let’s say we have an array {1, 2, 3, 6, 2, 3, 4, 7, 8} and integer K = 3.

The given array of length 9 can be split into 3 subsets {1, 2, 3}, {2, 3, 4} and {6, 7, 8} such that each subset consists of 3 consecutive elements.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The very first line of input contains an integer ‘T’ denoting the number of test cases. 

The first line of every test case contains two integers ‘N’ and ‘K’ where ‘N’ denotes the number of elements present in the array and ‘K’ denotes the size of each subset in which the array has to be divided so that it contains ‘K’ consecutive elements.

The second line of every test case contains ‘N’ space-separated integers denoting the elements present in the array.
Output format: 
For each test case, print a single line containing "True" or "False" depending on whether the array can be divided into ‘K’ sized subsets with 'K' consecutive elements.

The output for each test case is printed on a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= K <= N <=  5 * 10 ^ 4
1 <= ARR[i] <= 10 ^ 9

Where ‘ARR[i]’ represents the array element. 

Time Limit: 1 sec
Sample Input 1:
2
8 4
1 2 3 3 4 4 5 6 
4 3
1 2 3 4
Sample Output 1:
True
False
Explanation 1:
For the first test case, the array can be divided into [1,2,3,4] and [3,4,5,6]. So the answer is True.

For the second test case, the array cannot be divided into subsets of size 3 as N % K != 0. So the answer is False.
Sample Input 2:
2
6 3
3 3 2 2 1 1
12 3
3 2 1 2 3 4 3 4 5 9 10 11
Sample Output 2:
 True
 True
Hint

If the smallest number in the possible-to-split array is x, then numbers x + 1, x + 2, .…. x + k - 1 must contain there as well.

Approaches (1)
Divide the array in K sets of consecutive Elements

Approach:

 

  • In this approach, we will make a frequency hashmap to store the frequencies of all the array elements.
  • Now for every element present in the hashmap, we would check whether it forms a subset with the next (K - 1) elements or not. If so we will reduce the frequency of elements included in the subset from the hashmap and then proceed forward with the next element.
  • If any element is found which cannot be grouped in our subset of k consecutive elements then we will return False otherwise return True.

 

Algorithm:

  • First check whether N % K != 0 . If so, return False otherwise proceed with the below steps.
  • Take a hashmap ‘freq’ to store the frequencies of array elements.
  • Now traverse the hashmap and get the first smallest element from the map given by ‘start’.
  • Check whether there are ‘K’ consecutive numbers, then update the map.
    • If (start + i) where 0 <= i < K is present in the map then,
      • If freq[start + i] > 0 then freq[start + i]--.
      • If freq[start + i] becomes 0, then erase that element from ‘freq’.
    • Otherwise, return False if the next consecutive element is not found in the map.
  • Finally, return True if the map is empty.
Time Complexity

O(N * log(N)), where N is the number of elements in the array.

 

Storing the frequency of all array elements in the map will take O(N) time. Now traversing the map and updating the map will take O(N * log(N)) time. Thus total time complexity will be O(N + N * log(N)) = O(N * log(N)).

Space Complexity

O(N), where ‘N’ is the number of elements in the array.

 

O(N) extra space is required for the Hashmap. Hence, the overall space complexity is O(N). 

Code Solution
(100% EXP penalty)
Divide Array In K Sets Of Consecutive Numbers
Full screen
Console