Group Balls by Sequence

JavaView on GFG

Problem Overview

Group array elements into minimum number of subsequences where each is strictly increasing by 1.

Intuition

Group array elements into minimum number of subsequences where each is strictly increasing by 1.

Algorithm

1Sort array. Use a hashmap: count available sequences ending at value v. Place current in sequence ending at v-1.
2If no such sequence: start new one. If no sequence exists when needed: impossible.

Common Pitfalls

• Same as LC 659 (split into consecutive sequences). Greedy with end-count map.

Group Balls by Sequence.java

Java

// Approach: Greedy/sorting. Group consecutive balls following a sequence rule by sorting and scanning.
// Time: O(n log n) Space: O(n)
import java.util.*;

class Solution {
    public boolean validgroup(int[] arr, int k) {
        if (arr.length % k != 0)
            return false;

        TreeMap<Integer, Integer> countMap = new TreeMap<>();

        // Count frequencies
        for (int num : arr)
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);

        while (!countMap.isEmpty()) {
            int first = countMap.firstKey();

            for (int i = 0; i < k; i++) {
                int num = first + i;
                if (!countMap.containsKey(num))
                    return false;

                countMap.put(num, countMap.get(num) - 1);
                if (countMap.get(num) == 0)
                    countMap.remove(num);
            }
        }

        return true;
    }
}

Was this solution helpful?