Problem statement

https://binarysearch.com/problems/Split-List-Into-Strictly-Increasing-Chunks/

Solution

It is enough to check that we do not have frequency more than n/k. First of all, we if have frequency more than this number, we can not split due to pigeonhole principle. If we have less, then we can split, because we can distribute elements in groups [1, ..., n//k, 1, ..., n//k] and so on, each time taking all occurunces of element: in this way we can be sure that all elements in sets are different. I think I saw this problem on leetcode, but do not remember its number.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums, k):
        cnt = Counter(nums)
        n = len(nums)
        return all(x*k <= n for x in cnt.values())