📚 Interpreting the Problem

Imagine you’re given a list of limits, where each number in the list represents how many times that index can be used in total. You’re tasked with forming groups using numbers from 0 up to n-1, but with two essential conditions:

1. Each group must contain distinct numbers.
2. The size of each group must be strictly larger than the previous one.

Your goal is to determine the maximum number of such groups that can be formed. For instance, if your usage limits were [1, 2, 2], you could form 2 groups: [0] and [1,2]. The first has 1 number, the second has 2, and all numbers respect their usage limits.

🧠 First Attempts and Their Pitfalls

Initially, one might think of a greedy approach: use the most available numbers first and try to pack as many groups as possible. Starting with a group of size 1, then 2, then 3, and so on, seems like the natural path.

But there’s a subtle issue. Each time we increase the group size, we need more distinct numbers. And if we don’t carefully track which numbers are already overused, we may quickly run out of valid options. Worse yet, some numbers might be reusable in different groups (if allowed by the limit), so a naive one-pass assignment could be too rigid.

The complexity further increases when the number of potential groups approaches the higher end of constraints (possibly up to 10⁵). A naive attempt that tries to construct each group from scratch would likely fail due to time inefficiency. We need a way to decide whether it’s possible to form X groups efficiently, without actually building them.

💡 The Breakthrough Insight

The key realization is that instead of trying to build the actual groups, we can binary search on the number of groups and check if it’s possible to construct that many, given the usage limits.

Why binary search?

Because if it’s possible to form X groups, it must also be possible to form fewer than X. Conversely, if X groups aren’t possible, then neither are any greater number. This monotonicity allows us to use binary search to find the maximum valid X efficiently.

To validate whether a certain number X If groups are feasible, we simulate the process with some clever bookkeeping. We sort the elements by their usage limits, trying to use the largest ones first. Then, for each number, we try to contribute it to the current group count. If a number has leftover uses, we carry those into a priority queue to be distributed to future groups.

This insight is powerful because it separates the challenge into two manageable tasks.

• Determining feasibility (possible(X))
• Maximizing that value via binary search.

🔍 Walking Through the Algorithm (with Examples)

Let’s now walk through how the algorithm operates step by step!

The goal is to determine whether it is possible to form X groups that are strictly increasing in size, using the available usage limits.

1. We begin by sorting the usage limits in descending order. This allows us to use numbers with the highest flexibility first—those that can contribute to the most groups.
2. Then, for each value in the sorted list, we try to assign it to the remaining groups. The variable grpCnt tracks how many groups we’ve currently attempted to fill. At each step, the number of remaining groups to consider is X - grpCnt.
3. From the current number’s usage count, we determine how many groups we can help fill immediately. This is min(curr, X - grpCnt). Any leftover usage that we didn’t use immediately can be considered for filling previous group gaps, so we attempt to use it to satisfy any backlogged group needs stored in a max-heap. This heap keeps track of how many more elements are needed to complete previously attempted group sizes.
4. If there are still gaps after using the current number’s immediate and leftover capacity, we push those needs into the heap. Over time, this heap reflects unfilled group positions that need to be filled. If at the end, the heap is empty and we have tried to fill exactly X groups, then forming X groups is indeed possible.

By repeatedly applying this process for different values of X using binary search, we can efficiently find the maximum number of increasing-sized groups that can be formed under the given constraints.

Let’s now walk through a concrete example with usageLimits = <code>[7,10,4,5,7,4,5,3,5,6].

We will test whether it’s possible to form 10 strictly increasing groups, requiring sizes 1 through 10. That means we need a total of 55 distinct number uses.

Step 1: Sort usage limits in descending order

We pair each value with its index and sort descending by usage:

makefileCopyEditSorted: [(10,1), (7,4), (7,0), (6,9), (5,8), (5,6), (5,3), (4,5), (4,2), (3,7)]

Step 2: Simulate group formation with a heap

We simulate the logic in the possible() function using a heap (rest) to store leftover needs.

• grpCnt = 0, rest = empty heap

---

---

Final Check

• Heap is empty → all previous gaps filled
• grpCnt == X = 10 → successfully formed all groups

✅ Result: Success — we can form 10 increasing groups. In this case, several gaps emerged during the process (due to insufficient initial usage). Still, the leftover usage from other numbers was efficiently used to backfill those gaps via the heap.

This simulation provides a clear view of how each number contributes to group formation, how leftovers are managed, and how the algorithm avoids unnecessary computation by stopping early once all groups are formed.

📝 Pseudo Code

function possible(A, X):
    grpCnt = 0
    rest = empty max-heap
    for each (usage, index) in A:
        need = X - grpCnt
        used = min(usage, need)
        leftover = usage - used
        missing = need - used
        while leftover > 0 and rest is not empty:
            take top from rest
            fill from leftover
            push back if not filled
        if missing > 0:
            push missing into rest
        increment grpCnt
    return rest is empty and grpCnt == X

💻 Full Source Code

class Solution {
public:
    int N;

    // Helper function to determine if X groups can be formed
    bool possible(vector<pair<int,int>> & A, int X) {
        int grpCnt = 0;
        priority_queue<int> rest; // stores missing counts to be filled later

        for (int i = 0; i < N; ++i) {
            int curr = A[i].first; // current number's available usage
            int need = X - grpCnt; // number of groups left to form
            int used = min(curr, need); // how many we can use now

            int leftAfterUsed = curr - used;
            int needMore = need - used;

            // Try to use leftover capacity to fill previous group needs
            while(!rest.empty() && leftAfterUsed > 0) {
                int room = rest.top();
                rest.pop();
                int canAdd = min(room, leftAfterUsed);
                room -= canAdd;
                leftAfterUsed -= canAdd;
                if (room > 0) {
                    rest.push(room); // still more to fill
                }
            }

            // If we still have unfilled needs, push to heap
            if (needMore > 0) rest.push(needMore);

            if (grpCnt < X) grpCnt++;
        }

        return rest.empty() && grpCnt == X;
    }

    int maxIncreasingGroups(vector<int>& usageLimits) {
        N = (int)usageLimits.size();
        vector<pair<int,int>> A;
        for (int i = 0; i < N; ++i) {
            A.push_back({usageLimits[i], i});
        }
        sort(A.rbegin(), A.rend()); // Sort descending by usage

        int L = 0, R = 1e9;
        int ans = 0;
        while(L <= R) {
            int X = L + (R - L) / 2;
            if (possible(A, X)) {
                ans = X;
                L = X + 1;
            } else {
                R = X - 1;
            }
        }
        return ans;
    }
};

📌 Summary

The heart of this problem lies in recognizing the constraints of increasing group sizes and limited element usages. The clever use of binary search over group count, combined with a simulation via priority queues, allows us to handle large inputs efficiently. This technique is an excellent example of how feasibility functions and greedy heuristics can complement each other.