Check if an array can be split into subsets of K consecutive elements

0 0 5 minutes read

Given an array arr[] and integer K, the task is to split the array into subsets of size K, such that each subset consists of K consecutive elements.

Examples:

Input: arr[] = {1, 2, 3, 6, 2, 3, 4, 7, 8}, K = 3
Output: true
Explanation:
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.

Input: arr[] = [1, 2, 3, 4, 5], K = 4
Output: false
Explanation:
The given array of length 5 cannot be split into subsets of 4.

Approach
Follow the steps to solve the problem:

Store the frequencies of all array elements in a HashMap
Traverse the HashMap.
For every element present in the HashMap, check if all its occurrences can be grouped in a subsets with its next (K – 1) consecutive elements or not. If so, reduce the frequencies of the elements included in the subsets accordingly in the HashMap and proceed forward.
If any element is found which cannot be grouped into a subset of K consecutive elements, print False. Otherwise print True.

Below is the implementation of the above approach:

C++

// C++ Program to implement the
// above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a given array can
// be split into subsets of K consecutive
// elements
bool groupInKConsecutive(vector<int>& arr,
                         int K)
{
    // Stores the frequencies of
    // array elements
    map<int, int> count;
 
    for (int h : arr) {
        ++count[h];
    }
 
    // Traverse the map
    for (auto c : count) {
        int cur = c.first;
        int n = c.second;
 
        // Check if all its occurrences can
        // be grouped into K subsets
        if (n > 0) {
 
            // Traverse next K elements
            for (int i = 1; i < K; ++i) {
 
                // If the element is not
                // present in the array
                if (!count.count(cur + i)) {
                    return false;
                }
 
                count[cur + i] -= n;
 
                // If it cannot be split into
                // required number of subsets
                if (count[cur + i] < 0)
                    return false;
            }
        }
    }
 
    return true;
}
 
// Driver Code
int main()
{
    vector<int> arr = { 1, 2, 3, 6, 2,
                        3, 4, 7, 8 };
    int k = 3;
    if (groupInKConsecutive(arr, k)) {
        cout << "True";
    }
    else {
        cout << "False";
    }
}

Java

// Java Program to implement the
// above approach
import java.util.*;
class GFG{
 
// Function to check if a given array can
// be split into subsets of K consecutive
// elements
static boolean groupInKConsecutive(int[] arr,
                                    int K)
{
    // Stores the frequencies of
    // array elements
    HashMap<Integer,
              Integer> count = new HashMap<Integer,
                                           Integer>();
 
    for (int h : arr) 
    {
        if(count.containsKey(h))
            count.put(h, count.get(h) + 1);
        else
            count.put(h, 1);
    }
 
    // Traverse the map
    for (Map.Entry<Integer,
                    Integer> c : count.entrySet())
    {
        int cur = c.getKey();
        int n = c.getValue();
 
        // Check if all its occurrences can
        // be grouped into K subsets
        if (n > 0)
        {
 
            // Traverse next K elements
            for (int i = 1; i < K; ++i)
            {
 
                // If the element is not
                // present in the array
                if (!count.containsKey(cur + i)) 
                {
                    return false;
                }
 
                count.put(cur + i, count.get(cur + i) - n);
 
                // If it cannot be split into
                // required number of subsets
                if (count.get(cur + i) < 0)
                    return false;
            }
        }
    }
    return true;
}
 
// Driver Code
public static void main(String[] args)
{
    int[] arr = { 1, 2, 3, 6, 2,
                     3, 4, 7, 8 };
    int k = 3;
    if (groupInKConsecutive(arr, k))
    {
        System.out.print("True");
    }
    else
    {
        System.out.print("False");
    }
}
}
 
// This code contributed by sapnasingh4991

Python3

# Python3 program to implement the
# above approach
 
from collections import defaultdict
 
# Function to check if a given array can
# be split into subsets of K consecutive
# elements
def groupInKConsecutive(arr, K):
 
    # Stores the frequencies of
    # array elements
    count = defaultdict(int)
 
    for h in arr:
        count[h] += 1
 
    # Traverse the map
    for key, value in count.items():
        cur = key
        n = value
 
        # Check if all its occurrences can
        # be grouped into K subsets
        if (n > 0):
 
            # Traverse next K elements
            for i in range(1, K):
 
                # If the element is not
                # present in the array
                if ((cur + i) not in count):
                    return False
 
                count[cur + i] -= n
 
                # If it cannot be split into
                # required number of subsets
                if (count[cur + i] < 0):
                    return False
                     
    return True
 
# Driver Code
if __name__ == "__main__":
 
    arr = [ 1, 2, 3, 6, 2,
            3, 4, 7, 8 ]
    k = 3
     
    if (groupInKConsecutive(arr, k)):
        print("True")
    else:
        print("False")
 
# This code is contributed by chitranayal

C#

// C# program to implement the
// above approach
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
 
class GFG{
  
// Function to check if a given array can
// be split into subsets of K consecutive
// elements
static bool groupInKConsecutive(int[] arr,
                                int K)
{
     
    // Stores the frequencies of
    // array elements
    Dictionary<int,
               int> count = new Dictionary<int,
                                           int>();
  
    foreach(int h in arr) 
    {
        if (count.ContainsKey(h))
            count[h]++;
        else
            count[h] = 1;
    }
  
    // Traverse the map
    foreach(int c in count.Keys.ToList())
    {
        int cur = c;
        int n = count;
         
        // Check if all its occurrences can
        // be grouped into K subsets
        if (n > 0)
        {
             
            // Traverse next K elements
            for(int i = 1; i < K; ++i)
            {
                 
                // If the element is not
                // present in the array
                if (!count.ContainsKey(cur + i)) 
                {
                    return false;
                }
  
                count[cur + i] -= n;
  
                // If it cannot be split into
                // required number of subsets
                if (count[cur + i] < 0)
                    return false;
            }
        }
    }
    return true;
}
  
// Driver Code
public static void Main(string[] args)
{
    int[] arr = { 1, 2, 3, 6, 2,
                  3, 4, 7, 8 };
    int k = 3;
    if (groupInKConsecutive(arr, k))
    {
        Console.Write("True");
    }
    else
    {
        Console.Write("False");
    }
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
 
// Javascript Program to implement the
// above approach
 
// Function to check if a given array can
// be split into subsets of K consecutive
// elements
function groupInKConsecutive(arr, K)
{
    // Stores the frequencies of
    // array elements
    var count = new Map();
 
    arr.forEach(element => {
        if(count.has(element))
            count.set(element, count.get(element)+1)
        else
            count.set(element, 1)
 
    });
 
    // Traverse the map
 
    count.forEach((value, key) => {
         
        var cur = key;
        var n = value;
 
        // Check if all its occurrences can
        // be grouped into K subsets
        if (n > 0) {
 
            // Traverse next K elements
            for (var i = 1; i < K; ++i) {
 
                // If the element is not
                // present in the array
                if (!count.has(cur + i)) {
                    return false;
                }
 
                count.set(cur + i, count.get(cur+i)-n);
 
                // If it cannot be split into
                // required number of subsets
                if (count.get(cur + i) < 0)
                    return false;
            }
        }
    });
 
    return true;
}
 
// Driver Code
var arr = [1, 2, 3, 6, 2,
                    3, 4, 7, 8];
var k = 3;
if (groupInKConsecutive(arr, k)) {
    document.write( "True");
}
else {
    document.write( "False");
}
 
 
</script>

Output:

True

Time Complexity: O(N*log(N))
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!