Finding maximum groups in less time complexity

Question

I have an array of size n, array[i] represents the count of items of a particular type, where i is in range 0 to n-1.

I want to pack the items in groups following below rules:

• All items in a group should be distinct.
• The current group size must be strictly greater than the group formed in the previous batch.
• Also each item can be grouped only once, and it is not required to group every item.

Find the maximum number of groups we can create.

Note: The item types are numbered from 0 to n-1. So, the count of items of a particular type i (0 ≤ i ≤ n-1) is given by array[i].

Example n=5
array = [2, 3, 1, 4, 2]

An optimal way to create groups is:

1. The first group contains 1 item of item type 4. The remaining items = [2, 3, 1, 4, 1].
2. The second group contains 2 items of item types: 0 and 1. The remaining items = [1, 2, 1, 4, 1].
3. The third group contains 3 items of item types: 0, 1, and 3. The remaining items = [0, 1, 1, 3,1].
4. The fourth group contains 4 items of product types: 1, 2, 3, and 4. The remaining items = [0, 0, 0, 2, 0].

Finally, we have 2 items remaining, but our next group needs 5 items of different types (distinct). Therefore only 4 groups can be prepared, which is the maximum possible.

I have solved using below code:

import java.util.*;

public class Main {
    public static int solve(List<Integer> array) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int e : array) {
            if (e > 0) 
              maxHeap.offer(e);        
        }

        int groups = 0;
        int size = 1;
        while (true) {
            List<Integer> tempList = new ArrayList<>();
            int itemsAdded = 0;
            while (!maxHeap.isEmpty() && itemsAdded < size) {
                int count = maxHeap.poll();
                itemsAdded++;
                if (count > 1) {
                    tempList.add(count - 1);                
                }
            }

            if (itemsAdded < size) 
              break;

            for (int count : tempList) {
                maxHeap.offer(count);
            }

            groups++;
            size++;
        }
        return groups;
    }

    public static void main(String[] args) {
        // Test cases
        List<Integer> ar1 = Arrays.asList(2, 3, 1, 4, 2);
        System.out.println(solve(ar1)); // Output: 4

        List<Integer> ar2 = Arrays.asList(1, 2, 7);
        System.out.println(solve(ar2)); // Output: 3

        List<Integer> ar3 = Arrays.asList(1, 2, 8, 9);
        System.out.println(solve(ar3)); // Output: 4

        List<Integer> ar4 = Arrays.asList(12, 12, 11, 11, 8, 1, 1);
        System.out.println(solve(ar4)); // Output: 6
    }
}

constraints: n is in range 1 to 10^5 array[i] range is 0 to 10^9

If the input size is large, the above code fails with time-out errors, what is the correct approach to solve this problem in less time complexity.

Answer 1

The answer can be found through binary search. When verifying if we can form a certain number of groups, we attempt to add a single element to all unfinished groups at once each time, starting from the elements with the greatest frequency.

The time complexity is O(n log n).

public static int solve(List<Integer> counts) {
    counts.sort(Collections.reverseOrder());
    int low = 1, high = counts.size();
    while (low <= high) {
        int mid = low + high >>> 1, groups = 0, rem = mid;
        for (int i = 0; groups < mid && i < counts.size(); i++)
            if (counts.get(i) >= rem) {
                rem = mid - groups - 1 - Math.min(mid - groups - rem, counts.get(i) - rem);
                ++groups;
            } else rem -= counts.get(i);
        if (groups < mid) high = mid - 1;
        else low = mid + 1;
    }
    return high;
}