Find maximum difference between values in an array

Question

My task is to use the following pseudocode and improve it (make it run faster). Also I have to analyze the runtime of the given pseudocode and of my new code that i improved.

What does this algorithm do? It finds the smallest and greatest number in an array and creates the difference of them.

Pseudocode (given in task):

Input: Array Y, length n with n >= 2
Output: x (number)
x = 0
for i = 0 to n do
   for j = i + 1 to n do
      if x < A[i] - A[j] then
      x = A[i] - A[j];
      end if
   end for
end for
return x;

My code, improved:

public class Improved
{
    public static void main (String[] args)
    {
        int A[] = {1, 2, 3, 4, 5};
        int min = A[0];
        int max = A[0];

        for (int i = 0; i < A.length; i++)
        {
            if (min > A[i])
            {
                min = A[i];
            }

            if (max < A[i])
            {
                max = A[i];
            }
        }
        System.out.println(max - min);
    }
}

The only problem I got now is counting the runtime. I think for the pseudocode, it runs in \$\mathcal{O}(n^2)\$ because of the 2 for loops. Then my code will run in \$\mathcal{O}(n)\$, since it only has 1 for loop, right? :P What would be the worst case by the way?

Answer 1

What does this algorithm do? It finds the smallest and greatest number in an array and creates the difference of them.

Nope.

Consider {5, 2, 1}. The pseudo code returns 5 - 1 = 4 which happens to be the difference between the smallest and the largest value.

Now consider {1, 2, 5}. The pseudo code computes 1 - 2, 1 - 5, 2 - 5 and never updates x because all these values are < 0; the pseudo code then returns x, which is still 0. The difference between the largest and the smallest value, however, is still 5 - 1 = 4.

Answer 2

Code review

As others have pointed out, your code is not an improved version of the given pseudocode, but a different program altogether. Here's a review of your solution.

It's important to use meaningful, descriptive names for your program elements. It's impossible to guess what a class named "Improved" will do, and what a variable named "A" might be. Try to come up with better names.

Instead of putting some code in a main method, setting some hardcoded values, doing some logic and printing a result, it would be better to create a method with a single purpose, with a good name, input parameters and return value.

In the loop, you don't really need the loop index variable. In cases like this, it's strongly recommended to use an enhanced for-each loop instead.

The formatting of the code is also unusual, and doesn't follow common Java conventions.

Something like this would be better:

public class ArrayUtils {
    public static int findMaxDifference(int[] arr) {
        assert arr.length > 0;

        int min = arr[0];
        int max = arr[0];

        for (int value : arr) {
            if (min > value) {
                min = value;
            } else if (max < value) {
                max = value;
            }
        }
        return max - min;
    }
}

Note that the assert keyword serves mostly as documentation, in production code it has no effect, typically only enabled during unit test runners or debuggers.

The only problem I got now is counting the runtime. I think for the pseudocode, it runs in O(n^2) because of the 2 for loops. Then my code will run in O(n), since it only has 1 for loop, right? :P What would be the worst case by the way?

Not really a good Code Review question, but I'll answer anyway. Yes, the pseudocode compares every element with every other element, and so its runtime is proportional to \$N^2\$, and your algorithm iterates over the elements only once, so its runtime is proportional to \$N\$.

Answer 3

The only problem I got now is counting the runtime. I think for the pseudocode, it runs in O(n^2) because of the 2 for loops.

Correct.

Then my code will run in O(n), since it only has 1 for loop, right?

Correct.

What would be the worst case by the way?

O(n) as well. Best-case, worst-case, average-case, they are all O(n) here. You are always looping through the entire list once, no matter what.

---

Other comments:

Your code looks nice, the only thing I would improve would be some one variable name: A can be named input or numbers or similar. No need to use a one-character variable name for that.

A very minor issue is that your for loop can start at 1, as you use index 0 already to initialize min and max.

Answer 4

The pseudocode returns the maximum difference between an array item and one of its non-strictly following values

max { Aᵢ-Aⱼ : 0 ≤ i ≤ j < n }

As Taemyr explained, your code is equivalent to the math below instead of the above one:

max { Aᵢ-Aⱼ : 0 ≤ i < n, 0 ≤ j < n } = max { Aᵢ : 0 ≤ i < n } - min { Aᵢ : 0 ≤ i < n }

The first problem can also be computed in O(n) time.

max { Aᵢ-mᵢ : 0 ≤ i < n-1 }, mᵢ = min { Aⱼ : i ≤ j < n }

maxDiff = 0;
minNum = A[n-1];
for i=n-2 to 0
  if A[i]-minNum > maxDiff then
    maxDiff = A[i]-minNum;
  else if A[i] < minNum then
    minNum = A[i];
  end if
end for
return maxDiff;

Or iterating forwards,

max { Mᵢ-Aᵢ : 1 ≤ i < n }, Mᵢ = max { Aⱼ : 0 ≤ j ≤ i }

maxDiff = 0;
maxNum = A[0];
for i=1 to n-1
  if maxNum-A[i] > maxDiff then
    maxDiff = maxNum-A[i];
  else if A[i] > maxNum then
    maxNum = A[i];
  end if
end for
return maxDiff;

Answer 5

A really good habit to have is to separate out the different "concerns" in to separate functions. your main method does 3 things:

1. build a test dataset
2. compute the largest difference
3. print the result.

This leads to a main method which should look like:

public static void main (String[] args) {
    int[] data = testData();
    int maxDiff = maximumDifference(data);
    System.out.println(maxDiff);
}

The testData method would be easy to implement.

The maximumDifference method can have the single concern now of the basic computation. Note that Java8 has some nice streaming tricks:

public static int maximumDifference(int[] data) {
    IntSummaryStatistics stats = IntStream.of(data).summaryStatistics();
    if (stats.getCount() == 0) {
        return 0;
    }
    return stats.getMax() - stats.getMin();
}

There are some issues you may run in to. If someone puts values in tot he array that together exceed the Integer.MAX_VALUE limit, then the result will be wrong. It would be more correct to return a long value from the method, and convert the Min and Max values to longs before computing the diff. For example, what is the maximumDifference(...) in [2147483647, -100]

Answer 6

1

It would be nice to put the actual difference computing routine in its own method.

2

You can do a minor optimization. Instead of

if (min > A[i])
{
    min = A[i];
}

if (max < A[i])
{
    max = A[i];
}

you could write

if (min > A[i]) {
    min = A[i];
} else if (max < A[i]) {
    max = A[i];
}

since any element - except the first one - cannot be both a new maximum and a new minimum, we don't need to check the second condition above in case the first one passed.

3

The general Java coding conventions dictate that the opening brace is on the same line with the token it relates to, separated by a single space. So instead of

if (funky())
{
    yeah();
}

you should write

if (funky()) {
    yeah();
}

4

You should validate the input against being a null or an empty array, and throw an appropriate exception, in case something's fishy.

Summa summarum

Putting all points together, I had this in mind:

public class Main {

    public static int difference(final int... array) {
        if (array.length == 0) {
            throw new IllegalArgumentException("The input array is empty.");
        }

        int max = array[0];
        int min = array[0];

        for (final int i : array) {
            if (max < i) {
                max = i;
            } else if (min > i) {
                min = i;
            }
        }

        return max - min;   
    }


    public static void main(final String[] args) {
        System.out.println(difference(1, 2, 3, 4, 5));
    }
}

Hope that helps.