Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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;
      }
share|improve this question

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
    
Binary search is the better strategy! +1 –  Thomas Junk Jun 21 at 20:46
    
How does binary search help? –  bazang Jun 27 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 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.

share|improve this answer
    
I will say that using int[] is better. –  rolfl Jun 22 at 3:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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