# Finding the value 'n' in an array that has 'n' or more larger values

Given an unsorted array of integers, you need to return maximum possible $n$ such that the array consists at least $n$ values greater than or equals to $n$. Array can contain duplicate values.

Sample 1

input : [1, 2, 3, 4]
output: 2

Sample 2

input : [900, 2, 901, 3, 1000]
output: 3

What do you folks think of my code to this problem?

public static Integer findN(Integer[] values) {
Comparator comparator = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
};
Arrays.sort(values, comparator);
for (int i = 0 ; i < values.length; i++) {
if (i >= values[i]) {
return values[i];
}
}
return Integer.MIN_VALUE;
}
-

Right now, after you sort the array, you're doing a linear search for the correct value. I believe you should be able to write that part of the task using a binary search instead of a linear search.

The sorting has a minimum complexity of $O(N log N)$, so reducing the search from $O(N)$ to $O(log N)$ won't affect the overall computational complexity, but for any more than a small number of items, it should still reduce the overall time.

-
Binary search is the better strategy! +1 – Thomas Junk Jun 21 '14 at 20:46
How does binary search help? – bazang Jun 27 '14 at 1:59
@bazang: With a binary search, you can expect to look at approximately log N items to find your target. With a linear search, you can expect to look at approximately N/2 items instead. – Jerry Coffin Jun 27 '14 at 2:02

You haven't declared the Comparator with generics, only instantiated it with Generics. In fact, you get a compiler warning on the Arrays.sort line saying

Type safety: Unchecked invocation sort(Integer[], Comparator) of the generic method sort(T[], Comparator) of type Arrays

Better would be

Comparator<Integer> comparator = new Comparator<Integer>() {

There is nothing in the description saying that you should return Integer.MIN_VALUE for an empty array. I think it would be better to throw an exception.

There's no need to return an Integer when you can return int.

You're using generics so that you can use your own comparator. An alternative (not saying it's better or worse) would be to use pure int[], sort the array as usual, and then loop through the array backwards:

public static int findN(int[] values) {
Arrays.sort(values);
for (int i = values.length - 1; i >= 0; i--) {
int indexFromEnd = values.length - 1 - i;
if (indexFromEnd >= values[i]) {
return values[i];
}
}
throw new IllegalArgumentException("Array cannot be empty");
}

You might want to "fail-fast" instead and throwing the exception at the top, but then you'd have to throw an AssertionError or similar at the bottom.

-
I will say that using int[] is better. – rolfl Jun 22 '14 at 3:39