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>() {
            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;

2 Answers 2


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.

  • \$\begingroup\$ Binary search is the better strategy! +1 \$\endgroup\$ Commented Jun 21, 2014 at 20:46
  • \$\begingroup\$ How does binary search help? \$\endgroup\$
    – bazang
    Commented Jun 27, 2014 at 1:59
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Jun 27, 2014 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) {
    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.

  • \$\begingroup\$ I will say that using int[] is better. \$\endgroup\$
    – rolfl
    Commented Jun 22, 2014 at 3:39

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.