20. Group Balls by Sequence

✅ GFG solution to the Group Balls by Sequence problem: determine if balls can be grouped into consecutive sequences of length k using frequency mapping. 🚀

The problem can be found at the following link: 🔗 Question Link

🧩 Problem Description

You are given an array arr[] of positive integers, where each element arr[i] represents the number written on the i-th ball, and a positive integer k. Your task is to determine whether it is possible to rearrange all the balls into groups such that:

• Each group contains exactly k balls.

• The numbers in each group are consecutive integers.

📘 Examples

Example 1

Input: arr[] = [10, 1, 2, 11], k = 2
Output: true
Explanation: The balls can be rearranged as [1, 2], [10, 11].
There are two groups of size 2. Each group has 2 consecutive numbers.

Example 2

Input: arr[] = [7, 8, 9, 10, 11], k = 2
Output: false
Explanation: The balls cannot be rearranged into groups of 2,
since there are 5 balls, and 5 balls cannot be divided into groups of 2.

🔒 Constraints

• $1 \le \text{arr.size()} \le 10^6$

• $0 \le \text{arr}[i] \le 10^5$

• $1 \le k \le 10^3$

✅ My Approach

The optimal approach uses Frequency Mapping with Greedy Algorithm:

Frequency Map + Greedy Processing

1. Check Divisibility:

   • First, verify if the total number of balls is divisible by k.

   • If not, return false immediately.

2. Build Frequency Map:

   • Use a TreeMap (or sorted map) to store frequency of each number.

   • TreeMap ensures we process numbers in ascending order.

3. Greedy Group Formation:

   • For each number with non-zero frequency, try to form consecutive groups.

   • Starting from current number, check if next k-1 consecutive numbers exist.

   • Deduct the required frequency from all numbers in the sequence.

4. Validation:

   • If any consecutive number has insufficient frequency, return false.

   • Continue until all numbers are processed.

📝 Time and Auxiliary Space Complexity

• Expected Time Complexity: O(n log n + n _ k), where n is the array size. Building the frequency map takes O(n log n) time, and processing each element with k consecutive checks takes O(n _ k) time.

• Expected Auxiliary Space Complexity: O(n), as we use a frequency map to store at most n distinct elements.

🧑‍💻 Code (C++)

class Solution {
public:
    bool validgroup(vector<int> &arr, int k) {
        map<int, int> m;
        for (int x : arr) m[x]++;
        for (auto& p : m) {
            int v = p.first, f = p.second;
            if (f == 0) continue;
            for (int i = 1; i < k; i++) {
                if (m[v + i] < f) return false;
                m[v + i] -= f;
            }
        }
        return true;
    }
};

⚡ View Alternative Approaches with Code and Analysis

📊 2️⃣ TreeMap with Iterator Optimization

💡 Algorithm Steps:

1. Build a sorted map<int,int> of frequencies.

2. Traverse with an iterator, skipping zero counts.

3. For each non-zero entry (start, cnt), deduct cnt from each of the next k keys.

4. Return false if any required key has insufficient count.

class Solution {
public:
    bool validgroup(vector<int> &arr, int k) {
        map<int, int> freq;
        for (int val : arr) freq[val]++;

        auto it = freq.begin();
        while (it != freq.end()) {
            if (it->second == 0) { ++it; continue; }
            int start = it->first, cnt = it->second;
            for (int i = 0; i < k; i++) {
                if (freq[start + i] < cnt) return false;
                freq[start + i] -= cnt;
            }
            ++it;
        }
        return true;
    }
};

📝 Complexity Analysis:

• Time: ⏱️ O(n * k + n log n)

• Auxiliary Space: 💾 O(n)

✅ Why This Approach?

• Iterator-based traversal avoids redundant lookups.

• Cleaner code structure with early exits.

📊 3️⃣ Counting Sort Based Approach

💡 Algorithm Steps:

1. Find minVal and maxVal.

2. Build an array freq of size maxVal–minVal+1.

3. For each index i, if freq[i]>0, deduct from the next k slots.

4. Fail early if any slot lacks enough cards.

class Solution {
public:
    bool validgroup(vector<int> &arr, int k) {
        int mn = *min_element(arr.begin(), arr.end());
        int mx = *max_element(arr.begin(), arr.end());
        vector<int> freq(mx - mn + 1);
        for (int v : arr) freq[v - mn]++;
        for (int i = 0; i < freq.size(); i++) {
            int cnt = freq[i];
            if (cnt == 0) continue;
            for (int j = 1; j < k; j++) {
                if (i + j >= freq.size() || freq[i + j] < cnt)
                    return false;
                freq[i + j] -= cnt;
            }
        }
        return true;
    }
};

📝 Complexity Analysis:

• Time: ⏱️ O(n + range * k)

• Auxiliary Space: 💾 O(range)

✅ Why This Approach?

• O(1) array access instead of O(log n) map access.

• Better performance for bounded integer ranges.

📊 4️⃣ Greedy with Sliding Window

💡 Algorithm Steps:

1. Sort the array.

2. Build an unordered_map<int,int> of counts.

3. Iterate through sorted values; when cnt>0, deduct from next k consecutive keys.

4. Return false on any shortage.

class Solution {
public:
    bool validgroup(vector<int> &arr, int k) {
        sort(arr.begin(), arr.end());
        unordered_map<int, int> freq;
        for (int x : arr) freq[x]++;
        for (int x : arr) {
            int cnt = freq[x];
            if (cnt == 0) continue;
            for (int i = 0; i < k; i++) {
                if (freq[x + i] < cnt) return false;
                freq[x + i] -= cnt;
            }
        }
        return true;
    }
};

📝 Complexity Analysis:

• Time: ⏱️ O(n log n + n * k)

• Auxiliary Space: 💾 O(n)

✅ Why This Approach?

• Unordered_map for O(1) average access time.

• Sorted processing ensures optimal grouping.

🆚 🔍 Comparison of Approaches

🚀 Approach	⏱️ Time Complexity	💾 Space Complexity	✅ Pros	⚠️ Cons
🔍 Map Ultra-Optimized	🟢 O(n log n + n * k)	🟢 O(n)	⚡ Cleanest, most readable	🧮 Map overhead
🔄 TreeMap Iterator	🟢 O(n log n + n * k)	🟢 O(n)	🔧 Iterator efficiency	🐢 Still map-based
🔺 Counting Sort	🟢 O(n + range * k)	🟢 O(range)	🚀 O(1) access, fastest for bounded	🧮 Only works for bounded ranges
📊 Greedy Sliding	🟢 O(n log n + n * k)	🟢 O(n)	🏎️ Unordered_map speed	💾 Extra sorting step

🏆 Best Choice Recommendation

🎯 Scenario	🎖️ Recommended Approach	🔥 Performance Rating
⚡ General case, clean code	🥇 Map Ultra-Optimized	★★★★★
🔧 Bounded integer range (≤ 10^5)	🥈 Counting Sort	★★★★★
📊 Large datasets, hash-friendly	🥉 Greedy Sliding	★★★★☆
🏎️ Iterator-heavy processing	🏅 TreeMap Iterator	★★★☆☆

🧑‍💻 Code (Java)

class Solution {
    public boolean validgroup(int[] arr, int k) {
        Map<Integer, Integer> m = new TreeMap<>();
        for (int x : arr) m.put(x, m.getOrDefault(x, 0) + 1);
        for (Map.Entry<Integer, Integer> e : m.entrySet()) {
            int v = e.getKey(), f = e.getValue();
            if (f == 0) continue;
            for (int i = 1; i < k; i++) {
                if (m.getOrDefault(v + i, 0) < f) return false;
                m.put(v + i, m.get(v + i) - f);
            }
        }
        return true;
    }
}

🐍 Code (Python)

from collections import Counter
class Solution:
    def validgroup(self, arr, k):
        m = Counter(arr)
        for v in sorted(m.keys()):
            f = m[v]
            if f == 0: continue
            for i in range(1, k):
                if m[v + i] < f: return False
                m[v + i] -= f
        return True

🧠 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count

Visitor counter