Check if an array can be split into subsets of K consecutive elements
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:
Instead of a HashMap, you can use an array or another data structure to store the frequencies of array elements. This can lead to better performance since direct array access is typically faster than hashmap lookups.
Instead of traversing the entire HashMap, you can optimize the traversal by iterating over the array directly and checking for consecutive elements.
The description mentions grouping elements with their next (K – 1) consecutive elements. It’s important to clarify whether these consecutive elements are strictly consecutive or if there can be gaps between them.
- Sort the array to simplify consecutive element checking.
- Iterate through the sorted array and check if each element can be grouped with the next (K – 1) elements.
- If any element cannot be grouped into a subset of K consecutive elements, return False. Otherwise, return True.
Below is the implementation of the above approach:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool canSplitArray(vector<int>& arr, int K) {
int n = arr.size();
// Sort the array to simplify consecutive element checking
sort(arr.begin(), arr.end());
// Iterate through the sorted array and check for consecutive elements
for (int i = 0; i < n - K + 1; i++) {
// Check if each element can be grouped with the next (K - 1) elements
if (arr[i + K - 1] - arr[i] != K - 1) {
return false;
}
}
return true;
}
int main() {
vector<int> arr1 = {1, 2, 3, 6, 2, 3, 4, 7, 8};
int K1 = 3;
cout << "Output for arr1: " << boolalpha << canSplitArray(arr1, K1) << endl; // Output: true
vector<int> arr2 = {1, 2, 3, 4, 5};
int K2 = 4;
cout << "Output for arr2: " << boolalpha << canSplitArray(arr2, K2) << endl; // Output: false
return 0;
}
import java.util.Arrays;
public class SplitArrayIntoSubsets {
public static boolean canSplitArray(int[] arr, int K) {
int n = arr.length;
// Sort the array to simplify consecutive element checking
Arrays.sort(arr);
// Iterate through the sorted array and check for consecutive elements
for (int i = 0; i < n - K + 1; i++) {
// Check if each element can be grouped with the next (K - 1) elements
if (arr[i + K - 1] - arr[i] != K - 1) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int[] arr1 = {1, 2, 3, 6, 2, 3, 4, 7, 8};
int K1 = 3;
System.out.println("Output for arr1: " + canSplitArray(arr1, K1)); // Output: true
int[] arr2 = {1, 2, 3, 4, 5};
int K2 = 4;
System.out.println("Output for arr2: " + canSplitArray(arr2, K2)); // Output: false
}
}
def can_split_array(arr, K):
arr.sort()
for i in range(len(arr) - K + 1):
if arr[i + K - 1] - arr[i] != K - 1:
return False
return True
arr1 = [1, 2, 3, 6, 2, 3, 4, 7, 8]
K1 = 3
print("Output for arr1:", can_split_array(arr1, K1)) # Output: True
arr2 = [1, 2, 3, 4, 5]
K2 = 4
print("Output for arr2:", can_split_array(arr2, K2)) # Output: False
using System;
using System.Linq;
public class Program
{
public static bool CanSplitArray(int[] arr, int K)
{
Array.Sort(arr);
for (int i = 0; i < arr.Length - K + 1; i++)
{
if (arr[i + K - 1] - arr[i] != K - 1)
{
return false;
}
}
return true;
}
public static void Main(string[] args)
{
int[] arr1 = { 1, 2, 3, 6, 2, 3, 4, 7, 8 };
int K1 = 3;
Console.WriteLine("Output for arr1: " + CanSplitArray(arr1, K1)); // Output: true
int[] arr2 = { 1, 2, 3, 4, 5 };
int K2 = 4;
Console.WriteLine("Output for arr2: " + CanSplitArray(arr2, K2)); // Output: false
}
}
function canSplitArray(arr, K) {
arr.sort((a, b) => a - b);
for (let i = 0; i < arr.length - K + 1; i++) {
if (arr[i + K - 1] - arr[i] !== K - 1) {
return false;
}
}
return true;
}
let arr1 = [1, 2, 3, 6, 2, 3, 4, 7, 8];
let K1 = 3;
console.log("Output for arr1:", canSplitArray(arr1, K1)); // Output: true
let arr2 = [1, 2, 3, 4, 5];
let K2 = 4;
console.log("Output for arr2:", canSplitArray(arr2, K2)); // Output: false
Output
True
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)