5

There is this really good interview question that I encountered somewhere recently and I wanted to ask you all geniuses what can be the most optimized solution for this. So the question is as follows : Given an array of integers, find a maximum number n such that there are atleast n array elements which are greater than n. The input array is unsorted.

e.g. :

Input : 1,2,5,7,8,10 Output : n = 4

Input : 0,2,7,8,19,5,45,9,23 Output : n = 6

One solution I could think of(if the array is sorted case) is a sequential scan of all elements in the array to find out min:n and max:n. Then increment integers between min:n to max:n and check out one by one. But this is O(N) solution. Can somebody suggest a better one ?
e.g. : for input 1 min:n = 2 and max:n = 5
then you would check for numbers 2,3 and 4 as the answer.

As from the answers, if the array is unsorted there is no better than O(N) solution. But the next question is what if the given array is sorted ?

pseudocode :
// this assumes sorted input.
pubic int findhighestIndex(List<Integer> input){
it min=0,max=0,n=0,maxIndex=0;
for(int i=0;i<input.size();i++){
    if( input.get(i)>(input.size()-i) ){
        max=input.get(i);
        maxIndex=i;
        min=input.get(i-1);
        break;
    }
    else if(input.get(i)<(input.size()-i)){
        max=min=input.get(i);
    }
}
int i=max;
while( i>=min && (input.size()-maxIndex)<i ){
i--;
}
System.out.println(i);
}


Update : This problem is also known as finding h-index

Improve this question
15
  • What does N in “O(N) solution” refer to? Also, is an upper bound on integer size or array size given? Commented Jul 2, 2013 at 1:58
  • N is the number of elements given in the array. Commented Jul 2, 2013 at 1:58
  • If the array is unsorted then you're not going to do better than O(N) Commented Jul 2, 2013 at 1:58
  • Ok. so the next question is what if the array is sorted. ? Commented Jul 2, 2013 at 1:59
  • I think i didn't make the question clear, I have just edited, can you check ? Commented Jul 2, 2013 at 2:04

6 Answers 6

Reset to default
9

Edit: just figured out the O(n) solution for the unsorted case :) see below!

Sorted:

This can be solved in O(log N) for a sorted array, by means of a binary search on n. I'll be using OP's notation here, where N = # of elements and n is the answer we are looking for.

If the array is sorted, it basically means we need to find a position [N - n] so that such position in the array contains a value greater than n - if it does, then there are at least n values greater than it, regardless of repeated values.

Note an answer is always possible, as in the worst case the answer would be 0, and there are always at least 0 elements greater than it. The answer always gets "easier" for lower values, obviously, as it is easier to find 1 element greater than 1, than 10 elements greater than 10. But more importantly, this function follows a monotonic (non-decreasing) behavior which allows us to use a binary search on it.

The idea is as follows:

int N = 9;
int arr[10] = {0,2,5,7,8,9,19,23,45};

int lo = 0, hi = N+1, mid;
while(hi-lo > 1){
    mid = (hi+lo)/2;
    if(arr[N-mid] > mid) lo = mid;
    else hi = mid;
}
n = lo; //highest value that worked

Breakdown: The array has size 9. A binary search may begin trying value n = 5, so we just check whether the 5th element from the end of the array is greater than 5. In this case, 8 > 5 so we can try a better answer. The search would then attempt 7, but the element at position [N-7] is 5, which is lower than 7 and does not satisfy our constraints. Thus the search's last attempt is the value 6, which returns true as 7 > 6.

Unsorted:

For the unsorted case, the idea is incredibly very similar! We can solve it in O(n) by using a Selection Algorithm to identify the [N-n]th element, and at each step divide the search space in the same manner as the binary search.

We begin by searching from [0] to [N-1] to find the median (N/2 th) element, and we can rearrange the array in another O(N) step such that the median element is placed in its correct position, and every element before it has a value <= median, while every element after it has a value >=median.

Now, if that value is greater than n (in this case N/2), we showed above there are at least n elements greater than n, and thus we only need to search further in the lower half of the array. (If the median value is lower than n, we instead consider only the greater half of the array)

Now, assuming median >= N/2 we will repeat the same process from index [0] to [N/2], using a selection "sort" in O(N/2), and so on, each time dividing the search space by 2.

C++ code is as follows:

int N = 9;
int arr[9] = {0,2,7,8,19,5,45,9,23};

int lo = 0, hi = N, mid;
while(hi-lo > 1){
  mid = (hi+lo)/2;
  std::nth_element(arr+lo, arr+mid, arr+hi);
  if(arr[mid] > N-mid) hi = mid;
  else lo = mid;
}
n = N-hi;

In the end, we achieve a complexity of O(N) + O(N/2) + O(N/4) + ... = O(2*N) = O(N)

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Consider bucket sort or radix sort as a simple hack to get ~linear complexity on unsorted arrays.
This is a terrific answer, but your solution in the unsorted case is suboptimal (and is only O(n) "on average": see The Complexity section for std::nth_element). See my implementation of the solution by William Gates for a practically faster algorithm that runs in guaranteed O(n) time.
4

No magic involved

If you've been reading the above and thought "How am I ever going to come up with that in an interview" or "Can I really trust this code has no bugs", then look no further! Let me introduce you to the happy world of 'formal program design'!

In this answer I'll explain how we can turn the problem statement into a pair of inequalities which in turn will force our binary search, so there's just one way to write it. I will also catch a couple of bugs and corner cases left out in the previous answers.

Setting it all up

Let's assume we have a sorted, non-empty array of size N=7.

N: 7
    i: 0 1 2 3 4 5 6
ar[i]: 3 3 4 5 6 6 7

What we really want is an i s.t.

ar[i] <= N-i-1

However, we want the largest one, that is the one furthest to the right, so it must be that

ar[i+1] > N-i-1

Getting formal

What we are going to do is to keep two variables lo and hi st. we always have

ar[lo] <= N-lo-1   (1)
ar[hi] > N-hi-1    (2)

(Notice the substitution of i+1 for hi in the second equation).

We will then carefully move the variables towards each other, until lo+1 = hi, at which point we have found the i we originally sought.

Now we need some starting values.

  • A choice for hi could be N. This is out of the range of the array, but we are never going to read it, so we'll just assume it is a huge value that satisfies equation (2).

  • It's harder for lo, because can we even be sure that such a value exists? NO! The array [7,8,9] has no index which satisfies the wanted property, and thus we have found our first corner case. We can assume that if any index satisfies (1) it must be 0, but we have to introduce a test to see if it is actually ok to proceed.

Sweet! We've avoided a nasty bug.

Plugging it into the code

Ok, at this point it's time to invoke binary search. Really the work is already done, and we simply write:

if ar[0] > N-0-1:
    panic("No solutions found!")

lo, hi = 0, N
while lo+1 != hi:
    mid = (lo + hi)/2
    if ar[mid] <= N-mid-1:
        lo = mid
    if ar[mid] > N-mid-1:
        hi = mid

print "The solution is ar[%d] = %d" % (lo, ar[lo])

(Notice that we can change the second if to an else, since the conditions are the inverses of each other)

The result

Running it on the original example gives us:

The solution is ar[2] = 4

For fun, I also tried to run "i Code 4 Food"'s code with the same array. I think he assumes the values are unique, since he returns

lo = 4

Which clearly doesn't work, since ar[4] = 6, and there are only two values after that.

Improve this answer

1 Comment

Oops, appears I didn't quite get the question, and that the result doesn't have to be in the array. Hope you'll enjoy this none the less.
2

There is no need for sorting.

If a[1...N] is the input array, then notice that that answer you are looking for is <= N.

So for every number i in 0 <= i <= N, we try to keep track of the number of elements > i.

To compute this in O(N) time, we allocate an array S of size N+1, initialized to zeroes.

The make a pass through a, and when you encounter an element a (= a[j]), if a > N, you increment S[N+1], else you increment S[a].

The number of elements > i will be given by S[i+1] + S[i+2] + ... + S[N+1].

We can compute this for each i, by going through S from N+1 to 1, and maintaining a cumulative sum.

Improve this answer

1 Comment

This is the simplest solution for unsorted input.
0

The answer given by 'i Code 4 Food' is absolutely brilliant.

But I think you can decide the starting point in another way (I do not know if this is any better).

Suppose that the element which satisfies the given conditions is n. Now suppose I want to select an element at random from the sorted array (let random variable for integer be X) then P( X > n) >= n/N (where N is total no. of elements in array).

But from Markov's Inequality we have P( X > n) <= E[X]/n. Here E[X] is the expectation value i.e. the mean in this case.

Considering above two inequalities we have n/N <= E[X]/n i.e. n^2 <= Sum

Consider e.g. Input : 1,2,5,7,8,10, we would have got from inequality n^2 <= 33 so n < 6. So we could have set our starting point here.

Improve this answer

2 Comments

Your approach is interesting.However I'm not sure, is this probabilistic approach?Could you elaborate more?
Yes this is a probabilistic approach. I am considering that an integer chosen at random from the given array is X and then I am considering the given conditions to obtain the inequalities.
0

Just another solution in case you are not allowed to sort.

O(N log M)

where:

N=number of elements in input

M=range of numbers in input

Algorithm:

Do binary search on the answer.

 First find max element(M) of input using linear scan.
 int lo=0, hi=M
 while(hi-lo>1)
 {
  int mid=(lo+hi)/2;
  int t=0;
  for(int i=0;i<N;i++)if(A[i]>mid)t++;
  if(t>=mid)lo=mid;
  else hi=mid-1;
 }
 return lo;

If you are doing in the range of integers, log M factor is only 32.

Improve this answer

1 Comment

isn't that typically written O(N loglogN)?
-1

Since my edit to William Gates' answer was rejected for "promoting a product or service" (what?), I've copied my code implementing his solution here. In C++, this can be implemented for any data set in guaranteed linear time as:

#include <algorithm>
#include <vector>

size_t solve(std::vector<int> const &input) {
    std::vector<size_t> counts(input.size() + 1, 0);
    for (auto val : input) {
        if (0 <= val)
            ++counts[std::min(static_cast<size_t>(val), input.size())];
    }
    size_t n{ input.size() };
    for (size_t numGreater{ counts[n] }; 0 < n
         && numGreater < n; numGreater += counts[--n]);
    return n;
}

Note that this requires O(N) additional memory, and O(N) time.

Improve this answer

1 Comment

Down-voter care to comment? I added the missing header files and missing static_cast to get the code to compile, in case that is what lead to confusion. I then ran this on both sample inputs provided by the OP, and both produce the expected result. Further, it is the only algorithm presented for unsorted input that runs in guaranteed O(N) time.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.