Tejav
#1608

Special Array With X Elements Greater Than or Equal X

Easy
ArrayBinary SearchSortingSortingTwo Pointers
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n log n)
Space
O(1)
O(1)
💡

Intuition

Time O(n log n)Space O(1)

By sorting the array first, we can efficiently determine how many elements are greater than or equal to each potential x value. This reduces the number of comparisons we need to make.

⚙️

Algorithm

5 steps
  1. 1Step 1: Sort the array in non-decreasing order.
  2. 2Step 2: Loop through each index i from 0 to n (length of the array).
  3. 3Step 3: Calculate x as the number of elements from index i to the end of the array (n - i).
  4. 4Step 4: If the current element is greater than or equal to x, return x.
  5. 5Step 5: If no valid x is found, return -1.
solution.py8 lines
1def specialArray(nums):
2    nums.sort()
3    n = len(nums)
4    for i in range(n + 1):
5        x = n - i
6        if i == n or nums[i] >= x:
7            return x
8    return -1
ℹ

Complexity note: The time complexity is O(n log n) due to the sorting step, while the subsequent loop runs in O(n). This is much more efficient than the brute-force approach.

  • 1Sorting the array allows us to efficiently determine how many elements are greater than or equal to potential x values.
  • 2The unique nature of x means we only need to find one valid solution.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.