Special Array With X Elements Greater Than or Equal X Leetcode Solution

Difficulty Level Easy
Frequently asked in Google
algorithms Array coding Hashing Interview interviewprep LeetCode LeetCodeSolutionsViews 3168

In the problem, “Special Array With X Elements Greater Than or Equal X”, we are given an array of non-negative integers. We need to find some integer X such that there are exactly X elements greater than or equal to it in the array. If there is no possible X that satisfies this condition, we need to output -1.

Example

1 2 3 4
-1
1 3 4 5
3

Approach(Brute Force)

It is certain that if there exists a solution X, then X will always be unique.

Proof:

Consider there are two solutions X and Y such that X != Y. Lets assume X < Y. Now, number of elements greater than or equal to X should be X as we consider it as a solution. But, since Y > X, there are Y elements greater than or equal to X such that X != Y. Hence our assumption of X being a solution is wrong unless X and Y are equal.

So, there is always a unique solution, if a solution exists. Now, it can also be concluded that if X is a solution, then the number of elements greater than/equal to it = X, which should be less than N, where N = size of the array(as the maximum number of elements possible = N).

So, if a solution X exists, then it must lie in the range [1, N].

We can check for every integer in the range [1, N] if the number of elements in the array that are greater than or equal to any integer in the range is equal to that integer itself. For example, consider Array = {1 , 3 , 4 , 5}. Now, 1 and 2 have 4 and 3 elements greater than or equal to them in the array respectively. Number of elements greater than/equal to 3 = 3. So, 3 is the only solution. Since we traverse the whole tree to find the number of elements greater than for every integer in the range: [1, N], this approach is slow.

Algorithm

  1. Run a loop from i = 1 to i = N to check for solution:
    • Count the number of elements greater than or equal to ‘i‘ in the array
      • If the count is equal to ‘i‘, return i
  2. Return -1;

Implementation of Special Array With X Elements Greater Than or Equal X Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

int specialArray(vector <int> &a)
{
    int n = a.size() , counter = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        counter = 0;
        for(int j = 0 ; j < n ; j++)
            if(a[j] >= i)
                counter++;
        if(counter == i)
            return i;
    }
    return -1;
}

int main()
{
    vector <int> a = {1 , 3 , 4 , 5};
    cout << specialArray(a) << '\n';
}

Java Program

class special_array
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 4 , 5};
        System.out.println(specialArray(a));
    }

    static int specialArray(int[] a)
    {
        int n = a.length , counter = 0;
        for(int i = 1 ; i <= n ; i++)
        {
            counter = 0;
            for(int j = 0 ; j < n ; j++)
                if(a[j] >= i)
                    counter++;
            if(counter == i)
                return i;
        }
        return -1;
    }
}
3

Complexity Analysis of Special Array With X Elements Greater Than or Equal X Leetcode Solution

Time Complexity

O(N * N), N = Size of the array. In the worst case, when X = N is the solution, we make O(N * N) comparisons.

Space complexity

O(1). Only constant memory space is used.

Approach(Optimal)

We can store the number of occurrences of all elements in a table, using an array. Note that for any element with a value greater than N, we can count it as an occurrence of an element with value N because the maximum value of the solution can be N.

Now, the frequency of elements greater than or equal to X = frequency of X + frequency of all elements greater than X. In order to find this for every element in the range [1, N], we need to have a suffix frequency array.

So, for every integer in the array, we need to set frequency[i] = frequency[i] + frequency[i + 1], for every ‘i‘ in range [N – 1 , 1], which will create a suffix frequency array, storing number of elements greater than or equal to i  as frequency[i].

Now, because of the lookup table, we can check a solution for any integer in the range [1, N] in O(1) time. This is a case where we trade off memory to improve on time. Since the table is of size N, we have no worries of memory limits as well.

 

Special Array With X Elements Greater Than or Equal X Leetcode Solution

Algorithm

  1. Initialize a frequency array of size N, having each value as zero
  2. For every element i  in the array:
    1. If i > N, increment frequency[N]
    2. Increment frequency[i]
  3. Create a suffix sum array from frequency as:
    1. For every element ranging from i = N – 1 to i = 0
      1. set frequency[i] = frequency[i] + frequency[i + 1]
  4. Run a loop from i = 1 to i = N
    1. If i == frequency[i], return i
  5. return -1

Implementation of Special Array With X Elements Greater Than or Equal X Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

int specialArray(vector<int>& a)
{
    int n = a.size();
    vector <int> frequency(n + 1 , 0);
    for(int i = 0 ; i < n ; i++)
        if(a[i] > n)
            frequency[n]++;
        else
            frequency[a[i]]++;

    for(int i = n - 1 ; i >= 0 ; i--)
        frequency[i] += frequency[i + 1];

    for(int i = 0 ; i <= n ; i++)
        if(frequency[i] == i)
            return i;

    return -1;
}

int main()
{
    vector <int> a = {1 , 3 , 4 , 5};
    cout << specialArray(a) << '\n';
}

Java Program

class special_array
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 4 , 5};
        System.out.println(specialArray(a));
    }

    static int specialArray(int[] a)
    {
        int n = a.length;
        int[] frequency = new int[n + 1];
        for(int i = 0 ; i < n ; i++)
            frequency[i] = 0;

        for(int i = 0 ; i < n ; i++)
            if(a[i] > n)
                frequency[n]++;
            else
                frequency[a[i]]++;

        for(int i = n - 1 ; i >= 0 ; i--)
            frequency[i] += frequency[i + 1];

        for(int i = 0 ; i <= n ; i++)
            if(frequency[i] == i)
                return i;

        return -1;
    }
}
3

Complexity Analysis of Special Array With X Elements Greater Than or Equal X Leetcode Solution

Time Complexity

O(N), N = Size of the array. We can check for any integer in O(1) time, so in the worst case, we use O(N) time.

Space complexity

O(N). Linear memory space is used for storing frequencies.

Translate »