7
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ (Conventional wisdom suggests to compare pairs of array values, and only the smaller one to the min, the larger one to the max.) \$\endgroup\$ – greybeard Apr 30 '16 at 19:24
  • 1
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Simon Forsberg Apr 30 '16 at 20:13
  • \$\begingroup\$ And by the way, Y is also not a good variable name... \$\endgroup\$ – Simon Forsberg Apr 30 '16 at 20:13
  • \$\begingroup\$ How about using Enumerable.Max(A) - Enumerable.Min(A)? \$\endgroup\$ – Pete Oakey Apr 30 '16 at 23:48
  • \$\begingroup\$ I guess we should read Y as A in your pseudo code? \$\endgroup\$ – Édouard May 1 '16 at 1:23
9
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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;
            }
            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\$.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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;
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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]

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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