Finding the minimum or maximum

Finding the minimum/maximum is a common problem that can be phrased in a wide variety of ways. These include finding the min/max of:

the values in an array or ArrayList.
a fixed number of elements.
the results from running a method multiple times.
values calculated from the elements in an array or ArrayList.
values accepted as input.

There is a standard algorithm to find the min/max.

Algorithm for finding the min/max

Step 1: Store the min/max

Store something about the min/max value observed so far. Options include:

the position of the min/max in the array or ArrayList.
the value of the min/max itself.
a reference to the object that is the min/max.
information about or attributes of the min/max.

Ensure that the information stored is sufficient to:

identify a new min/max based on the desired criteria.
produce the desired result once all possible mins/maxes have been checked.
distinguish any required special cases (ex: no acceptable min/max found).

The value(s) being stored must be unambiguous, including any special values.

Step 2: Initialize the min/max

First thing that could be the min/max

If possible, initializing the min/max to the first thing that could be the min/max reduces the chance of errors.

AP CS A Free Response that require finding a min/max often either guarantee that there are at least a certain number of elements, or explicitly indicate what should be done if there are not enough elements (ex: return null).

Alternatives

If it is difficult or impossible to initialize the min/max to the first thing that could be the min/max, the initialization is even more important. The initial value(s) must ensure that the first min/max identified in Step 3 is stored as the min/max.

Options include:

the largest/smallest possible value (ex: Integer.MAX_VALUE / Integer.MIN_VALUE). Note the order. If finding the min, the min so far is initialized to the largest possible value (ex: Integer.MAX_VALUE)).
a special value that indicates that no min/max has yet been found. This value must be distinguishable from a valid value.

Some problems require that a special value be returned, or other task be performed, if no min/max can be found. The initial value(s) must ensure that it is possible to distinguish between an actual min/max and the absence of a min/max.

Step 3: Check each against min/max so far

Check each possible min/max against the min/max so far. Each time a smaller/larger value is found, update the min/max.

If the min/max is initialized to the first value, it may be possible to skip the first value.

In some problems, the possible min/max values are not elements in an array or ArrayList. A method might need to be called to obtain each value. The value might be calculated from elements in an array or ArrayList.

If the min/max so far is stored using more than 1 variable, each variable must be updated each time a new min/max is found.

Simple example with `int[]`

Method findMax returns the largest value in its parameter arr.

// precondition: arr.length > 0
public static int findMax(int[] arr)
{
    int max = arr[0];

    for(int i = 1; i < arr.length; i++)
        if(arr[i] > max)
            max = arr[i];
    
    return max;
}

Additional examples

Common mistakes

Common mistakes on AP CS A FR that require (or could have been avoided by) finding a min/max include:

initializing the min/max in a way that does not guarantee that a min/max will be properly identified in all cases. For example, if storing the value of the minimum, initializing it to 0 will fail if all of the values are positive.
failing to identify that the problem should be solved by finding the min/max (ex: getPrice method from the Trio FR).
storing the wrong information about the min/max (see below).
incorrectly obtaining the values to be checked against the min/max.
mishandling special cases.

Min/max on the AP CS A Multiple Choice

Questions on the AP CS A Multiple Choice might refer to finding the min/max. Treat each question carefully. Don’t assume that an approach doesn’t work just because it doesn’t follow the approach above. Programmers frequently encounter code written by others that may not match how we would have written the same code ourselves.

Examples: It is possible to initialize a variable that will hold a minimum value to Integer.MAX_VALUE. It is possible to handle the first value in an array in an unusual way. It is possible to find the min/max of a fixed number of values by explicitly comparing each value to each other value, though it is easy to mishandle specific cases.

Selected AP CS A FR that involve finding a min/max

Practice standard algorithms with AP CS Tutor Brandon Horn.

Help & comments

Get help from AP CS Tutor Brandon Horn

Comment on Finding the minimum or maximum