2790.Maximum_Number_of_Groups_With_Increasing_Length(Hard).md

2790. Maximum Number of Groups With Increasing Length (Hard)

Date and Time: Mar 26, 2025

Link: https://leetcode.com/problems/maximum-number-of-groups-with-increasing-length

Walk-through:

The inituitive approach will be using minHeap to solve this problem, but the time complexity for this one will be $O(n^2 log(n)$.

So, to solve this problem we observe a pattern that if we want to form a valid group with increasing length, each k group has to have k distinct elements with at least [1, 2, 3, ..., k], which is (k * (k+1)) / 2 elements, and we know it is guarantee to be distinct, we only need to make sure for each k group, we have the required elements.

Python Solution:

class Solution:
    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:
        # group=1: [1], group=2: [1, 2], group=3: [1,2,3]
        # 1. For group k, we need to have k different elements.
        # 2. sum([1,2,...,k]) = (k * (k+1)) / 2
        # Notice that we need to loop over usageLimits, so the max number of groups will be len(usageLimits).
        
        # TC: O(nlogn), n=len(usageLimits), SC: O(1)
        usageLimits.sort()
        groups, total = 0, 0
        for usage in usageLimits:
            total += usage
            # Check if groups + 1 can be formed, if so, we update groups = groups + 1
            if total >= ((groups + 1) * (groups + 2) / 2):
                groups += 1
        return groups

Time Complexity: $O(nlog(n))$
Space Complexity: $O(1)$