The problem does not provide constraints for [min, max] values in nums. Because of this, counting sort may be an option. We can build the sorted array using counting sort, then apply the same logic done in the provided solution to get down to O(n) time, in the worst case, but if max(nums) << len(nums), we can do even better, on average, by using a 'prefix sum'.

class Solution:
    def specialArray(self, nums):
        count = Counter(nums) # determine count of each number 
        largest = max(nums) # determine largest number in nums
        accumulate = [0] * (largest + 1) # build array of length len(n) + 1 to make indexing easier
        accumulate[largest] = count[largest] # initialize the tail of the array
        if accumulate[largest] == largest: # if largest occurs exac