Problem statement

https://leetcode.com/problems/divide-array-into-increasing-sequences/

Solution

Let m be the biggest frequency of number in our array. Notice, that if m*k > len(nums), than we can be sure, that we can not split our array into sequenes. Actually, what is true is the opposite as well: if we have m*k <= len(nums), then we always can split our array. Indeed if we allocate nums[i] to group with number i % m, then there will be no two equal elements in each group, also it means that each group will have at least k elements.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def canDivideIntoSubsequences(self, nums, k):
        return len(nums) >= max(Counter(nums).values()) * k