Calculating range of ArrayLists

Question

I have written this method which calculates the range (max - min) of an ArrayList. I have two for loops each for a different ArrayList. The for loops do exactly the same thing except they each use a different list, so I was wondering if there was a way to just use one for loop (or any other way) that does the work but iterates through both ArrayLists so that I don't have nearly identical for loops.

public static void calcRange(ArrayList <Integer> list1, ArrayList<Integer> list2){
    int max = list1.get(0);
    int min = list1.get(0);
    int max2 = list2.get(0);
    int min2 = list2.get(0);

    for (int i : list1){
        if ( i > max){
            max = i;
        } else if (i < min){
            min = i;
        }
    }
    for (int i : list2){
        if ( i > max2){
            max2 = i;
        } else if (i < min2){
            min2 = i;
        }
    }
    System.out.println("List 1 Range: "+(max - min)+"\tList 2 Range: "+(max2 - min2));
}

Answer 1

One way you can remove duplicated code is to create a method:

public static int[] GetMaxMin (ArrayList <Integer> list)
{
    int max = list.get(0);
    int min = list.get(0);

    for (int i : list){
        if (i > max) {
            max = i;
        } else if (i < min) {
            min = i;
        }
    }
    int[] maxMin = {max, min};

    return maxMin;
}

This can then be called like this:

max = GetMaxMin(list)[0];
min = GetMaxMin(list)[1];

However, the above said, I would not recommend doing this because it has two purposes - to get the max value and the min value in the list. What I would recommend is to implement two methods - one to get the max value and one to get the min value:

public static int GetMax (ArrayList <Integer> list)
{
    int max = list.get(0);

    for (int i : list){
        if (i > max) {
            max = i;
        }
    }

    return max;
}

GetMin would be similar. Then, all you would need to do is this:

int max = GetMax(list1);
int min = GetMin(list1);
int max2 = GetMax(list2);
int min2 = GetMin(list2);

As you are calculating a range of values, though, you should just write a method to do that:

public static int CalculateRange (ArrayList <Integer> list)
{
    int max = list.get(0);
    int min = list.get(0);

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

    return max - min;
}

As brought up in the comments, this will crash if there are 0 elements in the list. To prevent this, you should probably check this before you try to get the range, like this:

if (list.size() != 0) {
    System.out.printf("List 1 Range: %d\tList 2 Range: %d\n", CalculateRange(list1), CalculateRange(list2));
} else {
    System.out.println("There are no elements in this array");
}

Answer 2

Hosch250 and h.j.k. have the right idea here, to reduce the code to a function that returns the range (max - min) for each list. The function, according to Hosch250, will have the signature:

public static int CalculateRange (ArrayList <Integer> list)

I would recommend changing that to a more Java-standard capitalization of having a lower-case C in CalculateRange. i.e. calculateRange. Additionally, I would change the input type from ArrayList, to just Collection. There is no need to restrict the function to just one concrete type.

Finally, because you have the option, I would strongly recommend that you investigate the new Java 8 features which, in this case, would help a lot.

The idea would be to convert your Collection<Integer> to an int stream, and to then compute the IntSummaryStatistics you need.... something like:

public static int calculateRange(Collection<Integer> data) {
    IntSummaryStatistics stats = data.stream()
            .filter(d -> d != null)
            .mapToInt(d-> d.intValue())
            .summaryStatistics();
    return stats.count() == 0 ? 0 : stats.max() - stats.min();
}

Then, in your main method, I would also recommend the use of 'formatted' print, using the Format syntax

System.out.printf("List 1 Range: %d\tList 2 Range: %d\n",
        calculateRange(list1),
        calculateRange(list2));

Answer 3

The following section should be a method itself:

for (int i : list1){
    if ( i > max){
        max = i;
    } else if (i < min){
        min = i;
    }
}
// return max - min here

E.g. with the method name getRangeForList(List<Integer> list). Use interfaces such as List instead of the implementation (ArrayList) so that your code is not too restrictive.

Your calcRange() method can then be (using varargs so that you are not limited to just two arguments) :

public static void calcRange(List<Integer>... lists) {
    if (lists == null) {
        return;
    }
    int index = 0;
    for (final List<Integer> current : lists) {
        System.out.printf("List %d Range: %d\t", ++index, getRangeForList(current));
    }
    System.out.println();
}

Answer 4

Analysis

The current running time is 0(m+n) where m = length(list1) and n = length(list2). Combining the loops reduces the running time to 0(n) where n is the length of the longer list.

Single Loop Example

Procedure in psuedo code:

calcRange(list1, list2)

  length1 = list1.length
  length2 = list2.length

  stop = maximum(length1, length2)

  min1 = list1[0]
  max1 = list1[0]
  min2 = list2[0]
  max2 = list2[0]

  loop from i = 1 to stop
    
    if i< length1
      min1 = minimum(min1, list1[i])
      max1 = maximum(max1, list1[i])

    if i< length2
      min2 = minimum(min2, list2[i])
      max2 = maximum(max2, list2[i])

  end loop

  return list(min1, max1, min2, max2)

Further refactoring is possible, but not shown to make the high level structure read more clearly.

Semantics

In the review code there is a bit of disconnect between the form of the output and the execution path of the implementation:

• The output of the review code is in tuple value form - i.e. the results of both lists are treated as single value and returned simultaneously:

      System.out.println("List 1 Range: "+(max - min)+"\tList 2 Range: "+(max2 - min2));
  

• The review code execution path explicitly processes the lists sequentially making List2.range dependent on finding list1.range.

Double Loop

Looping over the array lists one at a time creates a compositional type dependency that could be abstracted as list2(list1()). As way of illustration:

process(list1)
print("List1 range: %d", (list1.max - list1.min))

process(list2)
print("\tList2 range: %d", (list2.max - list2.min))

Is structurally consistent with the 2 loop semantics because with two loops list1 has execution priority.

Single Loop

Using a single loop which partially processes both lists on each iteration directly reflects the tuple semantics of the output. The tuple output implies that the input is also a tuple.

Treating the input as a tuple is Java's default function semantics as well - it is not normal to assume that the first argument to a Java function of airity 2 has execution priority over the second argument. Multiple arguments are parsed to a random access structure, not into a sequential one.

Processing both loops in a single loop has the form of a fixed point calculation that converges toward the ordered pair value (list1.range, list2.range) with each iteration.

Partial Calculations

The single loop form allows for the possibility of returning the best current value of list1.range or list2.range at any time. This facilitates working with streams of arbitrary length and operating closer to real time.

Conclusions

Neither the single loop or double loop approach is objectively better. There are tradeoffs and benefits to each. These can only be evaluated in context. The hazard is that the context for a code snippet on the internet is often assumed to be trivial.