☕ DSA Java Articles

Topics › Arrays › Easy

Largest Element

Easy TUF ID 38 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a non-empty array of integers nums. Return the largest value it contains. If the maximum occurs more than once, any of those occurrences is the answer, because the question asks for the value, not its position.

Constraints: 1 ≤ n ≤ 10^5, every value fits in a 32-bit signed integer and may be negative.

Example 1

nums = [2, 5, 1, 3, 0]
answer = 5              // 5 is bigger than every other element

Example 2

nums = [-5, -2, -9, -2]
answer = -2             // all values are negative; the largest is the one closest to zero

Example 3

nums = [7]
answer = 7              // a single element is its own maximum

This is the simplest array problem on the sheet, and that is exactly why it is worth doing properly: the mistakes people make here (a bad initial value, mutating the input, forgetting the empty case) show up again in every harder scan.

Approach 1: Brute force, sort and take the last element

Intuition. A sorted array has its maximum at the end. So if we are allowed to spend O(n log n) time, sorting solves the problem with no thinking: sort, read the last slot. The method sorts a copy, because a function called “largest element” has no business reordering the caller’s data as a side effect.

Algorithm.

  1. Reject an empty array; it has no largest element.
  2. Clone nums and sort the clone in ascending order.
  3. Return the last element of the sorted clone.
static int bruteForce(int[] nums) {
    if (nums.length == 0) throw new IllegalArgumentException("empty array has no largest element");
    int[] copy = nums.clone();                   // never sort the caller's array just to read one value
    Arrays.sort(copy);
    return copy[copy.length - 1];
}

Complexity. Time O(n log n) for the sort; everything else is constant. Space O(n) for the copy (plus whatever the sort uses internally).

This does far more work than necessary. Sorting establishes the relative order of every pair of elements, while we only need to know which single element beats all the others. Comparison sorting cannot beat n log n, so the only way to go faster is to stop sorting.

Approach 2: Optimal, one linear pass

Intuition. Walk through the array once, remembering the biggest value seen so far. When the walk ends, that remembered value has been compared against every element and never lost, so it is the maximum. Each element is looked at exactly once, which is also a lower bound: an element you never looked at could have been the maximum, so no correct algorithm can do fewer than n reads.

The one design decision is the starting value. Start from nums[0], a real element of the array. Starting from 0 is a classic bug: for [-5, -2, -9] it would return 0, a number that is not even in the array. Starting from Integer.MIN_VALUE works for int but breaks the moment the code is adapted to long, so “first element” is the habit to form.

Algorithm.

  1. Reject an empty array.
  2. Set max = nums[0].
  3. For i from 1 to n - 1: if nums[i] > max, set max = nums[i].
  4. Return max.
static int optimal(int[] nums) {
    if (nums.length == 0) throw new IllegalArgumentException("empty array has no largest element");
    int max = nums[0];                           // start from a real element, not from 0
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > max) max = nums[i];
    }
    return max;
}

Dry run on nums = [2, 5, 1, 3, 0]:

i nums[i] max before nums[i] > max? max after
start       2
1 5 2 yes 5
2 1 5 no 5
3 3 5 no 5
4 0 5 no 5

The loop ends and 5 is returned.

Complexity. Time O(n): one comparison per element. Space O(1): a single variable.

Why is > and not >= the right comparison? Both return the same value, but > keeps the first occurrence of the maximum, which is what you want if you later extend the method to return an index as well. It also skips a needless write on every duplicate.

Approach 3: The same scan as a stream reduction

Intuition. Java’s IntStream has a max() operation that performs exactly the linear scan above. It returns an OptionalInt, because a stream can be empty, and getAsInt() unwraps it. We still check for emptiness up front so that all three methods fail in the same way on the same input.

Algorithm.

  1. Reject an empty array.
  2. Turn the array into an IntStream, call max(), unwrap the result.
static int optimalStream(int[] nums) {
    if (nums.length == 0) throw new IllegalArgumentException("empty array has no largest element");
    return IntStream.of(nums).max().getAsInt();
}

Complexity. Time O(n), space O(1); the stream pipeline is a thin wrapper around the loop.

Reach for this form in production code where readability wins. In an interview, write the explicit loop: it shows you know what the library is doing, and the loop is what you will adapt when the question changes to “the second largest” or “the largest and its index”.

Edge cases and pitfalls