Leetcode 1608. Special Array With X Elements Greater Than or Equal X

Problem statement

https://leetcode.com/problems/special-array-with-x-elements-greater-than-or-equal-x/

Solution

Sort values in decreasin order and then go from the start and continue until A[i] > i. In the end check if we have i == A[i].

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def specialArray(self, A):
        A, n, i = sorted(A)[::-1], len(A), 0
        while i < n and A[i] > i: i += 1
        return -1 if i < n and i == A[i] else i