Problem Statement
You are given an array of distinct positive integers. Your task is to split the array into the minimum number of subsets (or subsequences) such that every subset contains consecutive numbers.
Example 1
Input
arr = [100, 56, 5, 6, 102, 58, 101, 57, 7, 103, 59]
Output
3
Explanation
The minimum subsets are:
[5, 6, 7][56, 57, 58, 59][100, 101, 102, 103]
Therefore, the answer is 3.
Example 2
Input
arr = [10, 100, 105]
Output
3
Explanation
None of the numbers are consecutive.
[10][100][105]
Therefore, the answer is 3.
Observation
Instead of actually constructing the subsets, we only need to count how many consecutive sequences exist.
For example:
5 6 7 8
The sequence starts from 5 because 4 is not present.
Similarly,
100 101 102
The sequence starts from 100 because 99 is not present.
Key Idea
A number is the starting point of a new consecutive subset if its previous number (num - 1) does not exist in the array.
Each starting point represents exactly one consecutive subset.
Approach
Step 1
Store every array element inside a HashSet.
Why?
A HashSet allows checking whether a value exists in O(1) average time.
Step 2
Traverse every element in the array.
For every number, check:
if (!set.contains(num - 1))
If the previous number is missing, then the current number starts a new consecutive sequence.
Increment the answer.
Step 3
Return the total count.
Algorithm
Insert all array elements into a
HashSet.Initialize
count = 0.Traverse every element.
If
num - 1is not present in theHashSet, incrementcount.Return
count.
Java Solution
import java.util.HashSet;
class Solution {
int minSubsets(int arr[]) {
HashSet<Integer> set = new HashSet<>();
// Store every element
for (int num : arr) {
set.add(num);
}
int count = 0;
// Count sequence starting points
for (int num : arr) {
if (!set.contains(num - 1)) {
count++;
}
}
return count;
}
}
Code Explanation
Creating the HashSet
HashSet<Integer> set = new HashSet<>();
The HashSet stores every array element.
Example:
Input:
5 6 7 100 101
HashSet:
{5, 6, 7, 100, 101}
Searching in a HashSet takes O(1) average time.
Inserting Elements
for (int num : arr) {
set.add(num);
}
This loop inserts every element into the set.
Example:
arr = [5, 6, 7]
HashSet = {5, 6, 7}
Count Variable
int count = 0;
This stores the number of consecutive subsets.
Initially:
count = 0
Traversing the Array
for (int num : arr)
Each element is processed exactly once.
The Important Condition
if (!set.contains(num - 1))
This is the core idea of the solution.
We check whether the previous number exists.
Case 1
Suppose:
num = 5
Check whether 4 exists.
It does not.
Therefore, 5 starts a new subset.
Increment the count.
Case 2
Suppose:
num = 6
Check whether 5 exists.
It does.
Therefore, 6 already belongs to the subset that started at 5.
Do nothing.
Case 3
Suppose:
num = 100
Check whether 99 exists.
It does not.
Therefore, 100 starts another subset.
Increment the count.
Incrementing the Count
count++;
Whenever a starting point is found, increase the answer.
Returning the Result
return count;
Returns the minimum number of consecutive subsets.
Dry Run
Input
arr = [100,56,5,6,102,58,101,57,7,103,59]
HashSet
{5,6,7,56,57,58,59,100,101,102,103}
Join the conversation! Your thoughts help the community grow.