What is the time complexity of LeetCode 1608. Special Array With X Elements Greater Than or Equal X?

The Python solution on this page runs in O(n^2), where n is the length of the array.

What is the space complexity of LeetCode 1608. Special Array With X Elements Greater Than or Equal X?

The Python solution on this page uses O(1) auxiliary space.

Special Array With X Elements Greater Than or Equal X — LeetCode 1608 Python Solution

EasyArrayBinary SearchSorting

Problem: #1608
Pattern: Monotonic Stack
Reading time: 2 min
Source: leetcode.com

The problem

You are given an array nums of non-negative integers. nums is considered special if there exists a number x such that there are exactly x numbers in nums that are greater than or equal to x.

Example

Input: nums = [3,5]
Output: 2
Explanation: There are 2 values (3 and 5) that are greater than or equal to 2.

Python solution

Python

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        for x in range(1, len(nums) + 1):
            cnt = sum(v >= x for v in nums)
            if cnt == x:
                return x
        return -1

Complexity

Measure	Complexity
Time	O(n^2), where n is the length of the array
Space	O(1) auxiliary

Pattern: Monotonic Stack

Answer "what is the next greater element" for every position in one pass. LeetCode 1608. Special Array With X Elements Greater Than or Equal X is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1608. Special Array With X Elements Greater Than or Equal X?: LeetCode 1608. Special Array With X Elements Greater Than or Equal X is rated Easy on LeetCode.
What is the time complexity of LeetCode 1608. Special Array With X Elements Greater Than or Equal X?: The Python solution on this page runs in O(n^2), where n is the length of the array.
What is the space complexity of LeetCode 1608. Special Array With X Elements Greater Than or Equal X?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 1608. Special Array With X Elements Greater Than or Equal X cover?: LeetCode 1608. Special Array With X Elements Greater Than or Equal X is tagged Array, Binary Search and Sorting on LeetCode.