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

EasyArrayBinary SearchSorting
Leetcode Link

Problem Description

You are provided with an array called nums that contains non-negative integers. The array is classified as special if you can find a number x which meets a particular condition. The condition is that the count of numbers within the array nums that are greater than or equal to x must be exactly equal to x. It is important to note that x doesn't need to be a part of the nums array.

Your task is to find and return the number x if the array meets the criteria of being special. In the case where the array is not special, you should return -1. It is also mentioned that if an array is special, the value of x that satisfies the condition is always unique.

Intuition

The core idea to solve this problem efficiently is based on the realization that a sorted array makes it easier to find the count of elements greater than or equal to a given value. To elaborate, once nums is sorted, you can determine how many numbers are greater than or equal to x by finding the position of the first number in nums that is at least x and then calculating the number of elements after it in the array.

Here's how the thinking progresses towards a solution:

  1. Sort the array. In Python, this can be achieved using nums.sort().
  2. Iterate through potential x values, starting from 1 to the size of the array n. For each potential x, use a binary search to find the leftmost position where x could be inserted into the array without violating the sorted order. This operation tells us the count of elements greater than or equal to x by subtracting the insertion index from the length of the array n. In Python, this can be achieved using bisect_left(nums, x) which is imported from the bisect module.
  3. For each x, if the count of elements greater than or equal to x is equal to x itself, we have found the special value and return it.
  4. If none of the x values meet the condition, then the array is not special, and we return -1.

By using the sorted array and binary search, we can determine the count of elements >= x quickly for each x, allowing us to find the special value or determine that it does not exist with a good time efficiency.

Learn more about Binary Search and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How does quick sort divide the problem into subproblems?

Solution Approach

The implementation of the solution uses several straightforward steps following an algorithmic pattern that takes advantage of array sorting and binary search - a common pattern when dealing with ordered datasets.

Let's break down the solution step-by-step:

  1. Sorting: The input array nums is sorted in non-decreasing order. This is done to leverage the ordered nature of the array in subsequent steps which is essential for binary search. In Python, we achieve this using the nums.sort() method which sorts the list in place.

  2. Binary Search: To find out how many numbers are greater than or equal to a number x, we can perform a binary search to find the index of the first number in nums that is equal to or greater than x. The bisect_left function from the bisect module is used here which takes a sorted list and a target value x, then finds the leftmost insertion point for x in the list. The use of bisect_left ensures we have an efficient O(log n) lookup for the index.

  3. Loop Over Potential x Values: We know x can be at most the length of the array n. The solution iterates x from 1 through to n inclusive, checking if any of these values satisfy the special condition.

  4. Counting Greater or Equal Elements: For each x, the solution calculates the number of elements greater than or equal to x. This is done using n - bisect_left(nums, x). The bisect_left function gives us the index at which x could be inserted to maintain the list's sorted order. Therefore, the count of numbers greater than or equal to x is the length of nums minus this index.

  5. Verification and Return: The loop checks whether each x value equals the count of elements greater than or equal to x. When it finds a match (cnt == x), it returns x because we've found the unique number that makes the array special. If no such x is found by the time the loop ends, the solution returns -1, indicating that the array is not special.

The pattern followed here is a classic example of combining sorting with binary search to optimize the lookup steps, common in many algorithmic problems for reducing time complexity.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Example Walkthrough

Let's go through an example to illustrate the solution approach. Suppose our given nums array is [3, 6, 7, 7, 0].

  1. Sorting: First, we need to sort the array nums. After sorting, it becomes [0, 3, 6, 7, 7].

  2. Binary Search: We will use binary search to find the position for potential x values. For example, if we're checking for x = 3, we want to find the index where 3 could be inserted.

  3. Loop Over Potential x Values: We start checking for all potential x values starting from 1 up to the length of the array, which is 5 in this case. So, our potential x values are 1, 2, 3, 4, 5.

  4. Counting Greater or Equal Elements: We calculate the count of elements greater than or equal to x for each x. For instance:

    • For x = 1, binary search (bisect_left) insertion index in sorted nums is 0. The count is 5 - 0 = 5.
    • For x = 2, binary search insertion index is 1. The count is 5 - 1 = 4.
    • For x = 3, binary search insertion index is 1. The count is 5 - 1 = 4.
    • For x = 4, binary search insertion index is 2. The count is 5 - 2 = 3.
    • For x = 5, binary search insertion index is 5. The count is 5 - 5 = 0.

  5. Verification and Return: We check each x against the count of elements greater or equal to it:

    • For x = 1, 5 != 1. No match.
    • For x = 2, 4 != 2. No match.
    • For x = 3, 4 != 3. No match.
    • For x = 4, count = 3, and x = 4 do not match. No match.
    • For x = 5, count = 0, and x = 5 do not match. No match.

Since none of the potential x values resulted in the count being equal to x itself, we return -1. Therefore, the example array [3, 6, 7, 7, 0] is not special according to the problem statement.

Solution Implementation

1from bisect import bisect_left
2
3class Solution:
4    def specialArray(self, nums: List[int]) -> int:
5        # Sort the input array.
6        nums.sort()
7      
8        # Find the length of the nums array and store it in a variable n.
9        n = len(nums)
10
11        # Iterate through potential special values (x).
12        for x in range(1, n + 1):
13            # Use binary search (bisect_left) to find the leftmost position in nums
14            # where x could be inserted, then subtract it from n to get the count 
15            # of elements greater than or equal to x.
16            count_greater_or_equal_to_x = n - bisect_left(nums, x)
17          
18            # Check if count is equal to x (which is our definition of a special array).
19            if count_greater_or_equal_to_x == x:
20                # If it is a special array, return x.
21                return x
22              
23        # If no special value is found, return -1.
24        return -1
25
1class Solution {
2    public int specialArray(int[] nums) {
3        // Sort the array to enable binary search
4        Arrays.sort(nums);
5        int n = nums.length; // Get the length of the sorted array
6      
7        // Iterate through possible values of x
8        for (int x = 1; x <= n; ++x) {
9            int left = 0; // Initialize left pointer of binary search
10            int right = n; // Initialize right pointer of binary search
11          
12            // Perform binary search to find the first position where the value is >= x
13            while (left < right) {
14                int mid = (left + right) >> 1; // Calculate the middle index
15                if (nums[mid] >= x) {
16                    // If mid value is >= x, shrink the right end of the search range
17                    right = mid;
18                } else {
19                    // If mid value is < x, shrink the left end of the search range
20                    left = mid + 1;
21                }
22            }
23          
24            // Calculate the count of numbers >= x
25            int countGreaterOrEqualX = n - left;
26          
27            // If the count of numbers >= x equals x, we found the special value
28            if (countGreaterOrEqualX == x) {
29                return x; // Return the special value of x
30            }
31        }
32      
33        // If no special value is found, return -1
34        return -1;
35    }
36}
37
1class Solution {
2public:
3    int specialArray(vector<int>& nums) {
4        // Calculate the size of the array
5        int size = nums.size();
6
7        // Sort the array in non-decreasing order
8        sort(nums.begin(), nums.end());
9
10        // Iterate for each potential special value 'x' starting from 1 to size of array
11        for (int x = 1; x <= size; ++x) {
12            // Calculate the count of numbers greater than or equal to 'x' using lower_bound
13            // which returns an iterator to the first element that is not less than 'x'.
14            // Subtracting this from the beginning of the array gives the number of elements
15            // less than 'x', and subtracting from 'size' gives the elements greater than or equal to 'x'.
16            int count = size - (lower_bound(nums.begin(), nums.end(), x) - nums.begin());
17
18            // If the number of elements greater than or equal to 'x' is exactly 'x',
19            // Then we found the special value 'x' and return it
20            if (count == x) {
21                return x;
22            }
23        }
24
25        // If no such 'x' exists, return -1
26        return -1;
27    }
28};
29
1// Function to find if there exists any integer x such that x is the number of elements
2// in nums that are greater than or equal to x. If such an x is found, return x, otherwise return -1.
3function specialArray(nums: number[]): number {
4    // Total number of elements in the array
5    const length = nums.length;
6    // Left bound of the binary search
7    let lowerBound = 0;
8    // Right bound of the binary search, cannot be more than the length of the array
9    let upperBound = length;
10
11    // Perform binary search
12    while (lowerBound < upperBound) {
13        // Calculate the middle index of the current search range
14        const mid = Math.floor((lowerBound + upperBound) / 2);
15        // Calculate the count of numbers that are greater than or equal to mid
16        const count = nums.reduce((accumulator, value) => accumulator + (value >= mid ? 1 : 0), 0);
17
18        // If count equals mid, we found a special number, so return it
19        if (count === mid) {
20            return mid;
21        }
22
23        // If count is greater than mid, we need to search in the upper half of the range
24        if (count > mid) {
25            lowerBound = mid + 1;
26        } else {
27            // If count is less than mid, we need to search in the lower half of the range
28            upperBound = mid;
29        }
30    }
31
32    // If we exit the loop without finding a special number, return -1
33    return -1;
34}
35
Not Sure What to Study? Take the 2-min Quiz：

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Time and Space Complexity

The provided Python code attempts to find a special array with a non-negative integer x. An array is special if the number of numbers greater than or equal to x is equal to x.

Time Complexity

The time complexity of the given code consists of two parts:

  1. Sorting the nums array.
  2. Performing a binary search for each value of x in the sorted nums array using the bisect_left function.

The sorting operation on an array of n elements has a time complexity of O(n log n).

The loop runs from 1 to n+1 times; in each iteration, a binary search is performed using the bisect_left function. The binary search has a time complexity of O(log n) for each search.

Considering that the binary search is performed n times, the total time complexity for all binary searches in the worst case is O(n log n).

Hence, the overall time complexity is dominated by the sorting and the n binary searches, which in combination yields a time complexity of O(n log n + n log n). This simplifies to O(n log n) since the sorting term is the dominant term and the additional n log n term does not change the asymptotic growth rate.

Space Complexity

The space complexity of the algorithm is determined by the space used besides the input array nums.

  1. Sorting is in-place, so it does not use additional space proportional to the input array.
  2. The binary search uses only a few variables such as x and cnt, which take up constant space.

There is no additional space that is dependent on the size of the input, thus the space complexity is O(1), which means it uses constant additional space.

In summary:

  • Time Complexity: O(n log n)
  • Space Complexity: O(1)

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following array represent a max heap?

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫