Group Balls by Sequence

JavaView on GFG

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?