Calculating the max difference between any 2 numbers from an array

How can I make this little program work a little faster?

The task is to calculate the max difference between any 2 numbers from an array of numbers. Target time is 1 sec, now it works in 1.1 sec.

I’ve tried BufferedReader, PrintWriter and nested loops (instead of Arrays.sort).

import java.util.Arrays;
import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] a = new int[sc.nextInt()];
        for (int i = 0; i < a.length; i++) {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        System.out.println(a[a.length - 1] - a[0]);
    }
}

Right now you’re doing this:

• For each value
  • Read value
  • Store value in array
• Sort array
• Subtract highest from lowest

That’s a lot of work and inefficient in multiple ways:

• You’re keeping track of every entered value (memory intensive)
• You’re sorting the array (computation-time intensive)

In reality you’re only interested in two values:

• Highest value so far
• Lowest value so far

Therefore you can just do something like this:

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int amount = sc.nextInt();
    int highest = Integer.MIN_VALUE;
    int lowest = Integer.MAX_VALUE;

    for (int i = 0; i < amount; i++) {
        int next = sc.nextInt();
        if(next > highest) {
            highest = next;
        } 

        if(next < lowest) {
            lowest = next;
        }
    }

    System.out.println(highest - lowest);
}

Notice how I’ve assigned initial values of int.min and int.max. You have to provide a default value and this basically allows any value to immediately replace it (unless you add int.min/max yourself).

As Tunaki commented: you should use an if instead of else if so in the case of a single value you end up with both min and max the same (and hence: 0 difference).

There is no array of values to be stored now and we don’t have to sort it either.

I won’t bother with a benchmark but it is definitely faster than what you had before (which might not have been benchmarked properly anyway).

As others have pointed out,
you can find the max and min elements in a single pass,
iterating over the input without storing in an array, and without sorting.
This approach would be $O(n)$ in time and $O(1)$ in space.

Instead of doing this in the main method,
there will be several benefits to put it in its own method:

• The name of the method should make the purpose of the logic self-explanatory
• Opens the possibility of unit testing
• Opens the possibility of code reuse, by making it easy to call from somewhere else

For example:

public int findMaxDifference(Scanner scanner) {
    int count = scanner.nextInt();
    assert count > 0;
    IntSummaryStatistics stats = IntStream.range(0, count).map(i -> scanner.nextInt()).summaryStatistics();
    return stats.getMax() - stats.getMin();
}

public static void main(String[] args) {
    System.out.println(findMaxDifference(new Scanner(System.in)));
}

Now it’s possible to add some unit tests to verify it actually works:

@Test
public void max_diff_in_1_5_7_should_be_6() {
    assertEquals(6, findMaxDifference(new Scanner("3n1n5n7n")));
}

@Test
public void max_diff_in_singletonlist_should_be_0() {
    assertEquals(0, findMaxDifference(new Scanner("1n5n")));
}

@Test
public void max_diff_in_10_1_5_should_be_9() {
    assertEquals(9, findMaxDifference(new Scanner("3n10n1n5n")));
}

@Test
public void max_diff_in_1_m2_m1_should_be_3() {
    assertEquals(3, findMaxDifference(new Scanner("3n1n-2n-1n")));
}

Don’t sort your array, because sorting takes O(n log n) time and O(n) space. You should be able to do this in O(n) time and O(1) space, if you simply keep track of the minimum and maximum values seen so far as you read the inputs. You don’t even need to store all of the inputs.