Problem of The Day: Special Array With X Elements Greater Than or Equal X

Problem Statement

Brute Force - Accepted

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        nums.sort()
        N = len(nums)
        max_num = max(nums)
        special = defaultdict(int)
        for i in range(max_num + 1):
            for num in nums:
                if num >= i:
                    special[i] += 1

            if special[i] == i:
                return i

        return -1

• Time: O(n^2)
• Space: O(1)

Editorial

Approach 1: Sorting

class Solution:
    def get_first_greater_or_equal(self, nums, val):
        start = 0
        end = len(nums) - 1

        index = len(nums)
        while start <= end:
            mid = (start + end) // 2

            if nums[mid] >= val:
                index = mid
                end = mid - 1
            else:
                start = mid + 1

        return index

    def specialArray(self, nums: List[int]) -> int:
        nums.sort()

        N = len(nums)
        for i in range(1, N + 1):
            k = self.get_first_greater_or_equal(nums, i)

            if N - k == i:
                return i

        return -1

• Time: O(nlogn)
• Space: O(n)

Approach 2: Counting Sort + Prefix Sum

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        N = len(nums)

        freq = [0] * (N + 1)
        for num in nums:
            freq[min(N, num)] += 1

        num_greater_than_or_equal = 0
        for i in range(N, 0, -1):
            num_greater_than_or_equal += freq[i]
            if i == num_greater_than_or_equal:
                return i

        return -1

• Time: O(n)
• Space: O(n)