Split Array into Minimum Subsets

Problem Overview

Partition distinct positives into the fewest subsets where each subset is a run of consecutive integers.

Intuition

Partition distinct positives into the fewest subsets where each subset is a run of consecutive integers. After sorting, consecutive numbers that belong together sit side by side, so each gap where arr[i] != arr[i-1] + 1 starts a new subset. The answer equals the number of such contiguous runs.

Algorithm

1Sort arr in non-decreasing order.
2Initialize count = 1 (at least one subset if the array is non-empty).
3For i from 1 to n-1: if arr[i] != arr[i-1] + 1, increment count.
4Return count.

Example Walkthrough

Input: arr = [100, 56, 5, 6, 102, 58, 101, 57, 7, 103, 59]

1. Sorted: [5,6,7,56,57,58,59,100,101,102,103].
2. Breaks after 7 and after 59 (next is not previous + 1).
3. Three runs: [5,6,7], [56..59], [100..103] -> answer 3.

Output: 3

Common Pitfalls

• Elements are distinct in the usual statement - duplicates would need a different rule.
• This counts subsets of consecutive values, not arbitrary subsequences with other constraints.
• Empty array edge case: the loop never runs; handle n = 0 if required by the judge.
• A hash-set approach also works in expected O(n): count values x where x-1 is absent.

Split Array into Minimum Subsets.java

Java


import java.util.*;

class Solution {

    // Approach: Partition into the fewest subsets of consecutive numbers. Sort
    // so consecutive values sit together, then count how many times the sorted
    // sequence breaks (arr[i] != arr[i-1] + 1). Each contiguous run is one subset.
    // Complexity: O(n log n) time and O(1) extra space (sort in place).
    int minSubsets(int arr[]) {
        Arrays.sort(arr);

        int count = 1;

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] != arr[i - 1] + 1) {
                count++;
            }
        }

        return count;
    }
}

Was this solution helpful?