Java  

Split Array into Minimum Subsets

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

  1. Insert all array elements into a HashSet.

  2. Initialize count = 0.

  3. Traverse every element.

  4. If num - 1 is not present in the HashSet, increment count.

  5. 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}
NumberPreviousExists?Count
10099No1
5655No2
54No3
65Yes3
102101Yes3
5857Yes3
101100Yes3
5756Yes3
76Yes3
103102Yes3
5958Yes3

Final Answer

3

Dry Run (Example 2)

Input

arr = [10,100,105]

HashSet

{10,100,105}
NumberPreviousExists?Count
109No1
10099No2
105104No3

Final Answer

3

Why Does This Work?

Consider the sequence:

20
21
22
23

Only 20 has no previous number because 19 is not present.

Therefore:

  • 20 starts the sequence.

  • 21 belongs to the sequence started by 20.

  • 22 belongs to the same sequence.

  • 23 also belongs to the same sequence.

So:

One starting point = One consecutive subset

Counting starting points automatically gives the minimum number of required subsets.

Complexity Analysis

Time Complexity

  • Building the HashSet: O(n)

  • Traversing the array: O(n)

  • HashSet lookup: O(1) average

Overall Time Complexity: O(n)

Space Complexity

The HashSet stores all array elements.

Overall Space Complexity: O(n)

Key Takeaways

  • Use a HashSet for constant-time lookups.

  • A number starts a new subset only if its previous number is absent.

  • Count the sequence starting points instead of constructing the subsets.

  • This approach solves the problem in O(n) time with O(n) extra space.

Summary

The minimum number of consecutive subsets is equal to the number of sequence starting points in the array. By storing all values in a HashSet and counting every element whose predecessor (num - 1) is missing, we can solve the problem efficiently in linear time without sorting or explicitly building the subsets. This makes the solution both simple and optimal for large inputs.

Membership not found