CODEWITHSUNDEEP
javaarrayssortingmaxmin
blueCloud
blueCloud

Reputation: 433

Efficient way for finding the min and max value in an array

I want to find out the minimum and maximum value in an array of integers.

Which one of the following ways would be the more efficient?

  1. Sort the array and then look at start and end to get the minimum and maximum.

  2. Convert the array into a list using Arrays.asList() and then use the Collections.min() method.

The code where I want to use this is the following:

// Find missing number from an array of consecutive numbers arranged randomly
import java.util.Arrays;

public class MissingNumber {

    public static void main(String[] args) {

        int[] consecutiveRandomNos = { 3, 6, 5 };

        System.out.println(addNumbers(consecutiveRandomNos));
        System.out.println("The missing number is "
                        + (returnSum(consecutiveRandomNos) - addNumbers(consecutiveRandomNos)));
    }

    public static int addNumbers(int... numbers) {
        int result = 0;

        for (int number : numbers) {
            result += number;
        }

        return result;
    }

    public static int returnSum(int... nos) {

        Arrays.sort(nos);

        int max = nos[nos.length - 1];

        int min = nos[0];

        int total = 0;

        for (int i = min; i <= max; i++) {
            total += i;
        }

        return total;
    }
}

Upvotes: 4

Views: 14112

Answers (3)

Daniel Langdon
Daniel Langdon

Reputation: 5999

Sort is O(Nlog(N)) at best. You can find min and max trivially in O(n) just iterating over the array.

int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i=0; i<array.length; i++)
{
    if(array[i] < min)
       min = array[i]
    if(array[i] > max)
       max = array[i]
}

Edit:

I noticed you pasted some extra code and that you actually want to find a missing number in an array of consecutive numbers. Rather than iterating all that much, there are mathematical summations that can help you here in O(1). In fact, you can solve the entire problem with a single for loop:

int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int sum = 0;
for(int i=0; i<array.length; i++)
{
    if(array[i] < min)
       min = array[i];
    if(array[i] > max)
       max = array[i];
    sum += array[i];
}

return (max - min + 1)(max + min)/2 - sum;

Upvotes: 8

Zielu
Zielu

Reputation: 8552

sorting costs O(NlogN), going through an array to find min and max costs O(N). No need for convertsion to list, just iterrate the array.

Upvotes: 4

Maroun
Maroun

Reputation: 95948

Collection#min source code:

585     public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) {
586         Iterator<? extends T> i = coll.iterator();
587         T candidate = i.next();
588 
589         while (i.hasNext()) {
590             T next = i.next();
591             if (next.compareTo(candidate) < 0)
592                 candidate = next;
593         }
594         return candidate;
595     }

It's O(n) in terms of time complexity. If your sorting algorithm is O(n) (post it please), they're both the same, again, in terms of time complexity.

Upvotes: 0

Related Questions