Find the Minimum Value in an Array

Given an array of integers, return its smallest element. If the array is empty, there is no minimum.

Example 1

Input:  [9, 2, 3, 6]
Output: 2

Example 2

Input:  [-7, 0, -7, 4]
Output: -7

Example 3

Input:  []
Output: empty (no minimum)

OptionalInt is a container that holds either one int or nothing. Returning OptionalInt makes the empty case explicit. Returning a sentinel like Integer.MAX_VALUE would be ambiguous: the array {Integer.MAX_VALUE} would give the same answer as {}.

Brute force: sort and take the first element

After sorting in ascending order, the minimum is at index 0. Sorting changes the order of the elements, so we sort a copy (Arrays.copyOf makes a new array with the same elements).

import java.util.Arrays;
import java.util.OptionalInt;

public class Main {
    static OptionalInt findMin(int[] nums) {
        if (nums.length == 0) return OptionalInt.empty();
        int[] sorted = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sorted);
        return OptionalInt.of(sorted[0]);
    }

    public static void main(String[] args) {
        System.out.println(findMin(new int[]{9, 2, 3, 6}));
        System.out.println(findMin(new int[]{-7, 0, -7, 4}));
        System.out.println(findMin(new int[]{}));
    }
}

OptionalInt[2]
OptionalInt[-7]
OptionalInt.empty

Time: O(n log n). Space: O(n) for the copy. Sorting puts every element in order when we only need one of them.

Optimal: one pass

Start with the first element as the current minimum. For every other element, replace the minimum when you find something smaller. An empty array returns OptionalInt.empty() before the loop runs.

Walkthrough with [9, 2, 3, 6]:

import java.util.OptionalInt;

public class Main {
    static OptionalInt findMin(int[] nums) {
        if (nums.length == 0) return OptionalInt.empty();
        int min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < min) {
                min = nums[i];
            }
        }
        return OptionalInt.of(min);
    }

    public static void main(String[] args) {
        System.out.println(findMin(new int[]{9, 2, 3, 6}));
        System.out.println(findMin(new int[]{-7, 0, -7, 4}));
        System.out.println(findMin(new int[]{}));
    }
}

OptionalInt[2]
OptionalInt[-7]
OptionalInt.empty

Time: O(n): every element has to be looked at, since any one of them could be the minimum, so no algorithm can do better on unsorted input. Space: O(1).

In real code

IntStream runs the same single pass. Arrays.stream(int[]) creates the stream, and min() returns an OptionalInt.

import java.util.Arrays;
import java.util.OptionalInt;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) {
        int[] nums = {9, 2, 3, 6};
        OptionalInt min = Arrays.stream(nums).min();
        int minIndex = IntStream.range(0, nums.length)
                .reduce((a, b) -> nums[b] < nums[a] ? b : a)
                .getAsInt();
        System.out.println(min + " " + minIndex);
    }
}

OptionalInt[2] 1

The reduce call keeps the index of the smaller value and keeps the earlier index on ties. For an ArrayList<Integer>, Collections.min(list) returns the minimum and throws NoSuchElementException on an empty list.

Edge cases

• Empty array: OptionalInt.empty().
• All equal: returns that value.
• Duplicate minimums: the value is the same whichever copy is found.