Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Find the Largest Element in an Array

Learn to keep a running maximum, reason about each comparison, and trace a one-pass Java solution.

EasyArraysPattern: array traversal, running answer

Problem statement

Given a nonempty Java integer array, return the largest value in it. Do not return the position of that value.

  • Input: an int[] containing at least one element.
  • Output: one int — the largest value in the array.
  • Negative numbers and duplicate values are allowed.
  • Do not modify the array or its order.
  • Aim for one pass and constant extra space.

Valid input versus defensive behavior

The problem assumes a nonempty array. For callers outside that assumption, our method throws IllegalArgumentException for null or an empty array. There is no sensible maximum to return in either case. This guard is separate from the search algorithm; it does not treat 0 as a missing answer.

Constraints & requirements

INPUT
A nonempty integer array
RETURN
The greatest value
TARGET
One pass and constant extra space

Examples 4 test cases

  1. Example 1 A mixed array

    Input
    [4, 7, 2, 9, 3]
    Output
    9

    The largest value is 9, at index 3. Return the value, not the index.

  2. Example 2 All negative

    Input
    [-8, -3, -11, -5]
    Output
    -3

    Rejects an unsafe initial answer of zero.

  3. Example 3 Single value

    Input
    [7]
    Output
    7

    Checks the smallest valid array.

  4. Example 4 Repeated maximum

    Input
    [4, 9, 2, 9]
    Output
    9

    Confirms duplicates do not change the result.

Hints Optional

Hints become more specific one step at a time.
01Choose a safe starting answer

A fixed value such as 0 is unsafe because the entire array may contain negative numbers.

02Keep a running best value

Start with the first element, then compare it with every value that follows.

03The loop invariant

After processing index i, the stored answer is the largest value from index 0 through i.

How to think before coding

Define largest as the maximum of the values already processed. Initialize it from an actual element, then ask only whether the next element can improve it. This tells you the loop boundary (start at index 1), the condition (>), the update (replace one variable), and the return value. No sorting, index result or second array is needed.

Brute force and the improvement

The direct scan is already the optimal baseline: keep the greatest value read so far. It takes O(n) time and O(1) extra space. To see why sorting is unnecessary, imagine sorting a copy, then returning its last value: that costs O(n log n) time and O(n) copy space, plus the sort’s workspace, even though the question asks for just one value. Sorting the original would also violate the no-modification requirement. No algorithm can skip an arbitrary unread value in the worst case: that value might be the largest.

Intuition

Imagine reading [4, 7, 2, 9, 3] from left to right. You do not need to remember every value. You only need to remember the best value seen so far.

Start with 4. Reading 7 improves the answer. Reading 2 does not. Then 9 improves it again, and 3 cannot beat 9.

Algorithm steps

  1. Reject null or empty input before accessing the first element.
  2. Set largest to values[0]. A real array value is a safe starting answer, including for an all-negative array.
  3. Start index at 1, because index 0 has already been processed.
  4. If values[index] > largest, replace largest. Otherwise, keep it.
  5. After the last element, return largest.

The processed prefix is the part we have finished checking. Everything to its right is still unread. A larger current value replaces the running maximum; a smaller or equal value leaves it unchanged.

The same running-answer idea appears in monitoring: as measurements arrive, one variable can track peak latency, the largest payload, or the highest queue depth. You keep the answer you need, rather than a sorted history of every measurement.

Java solution

The method reads the input without sorting or changing it. The comments explain the guard, initialization, comparison, and return.

Java
public static int largestElement(int[] values) {
    // Reject an array with no values: it has no maximum.
    if (values == null || values.length == 0) {
        throw new IllegalArgumentException("Array must not be empty");
    }

    // Start with an actual value, not zero, so all-negative inputs work.
    int largest = values[0];
    for (int index = 1; index < values.length; index++) {
        // Only a greater value can improve the maximum so far.
        if (values[index] > largest) {
            largest = values[index];
        }
    }
    return largest; // Every value has been checked.
}

Read the three key decisions

  • Initialize from the array: values[0] is always a valid candidate. Starting from 0 would create a candidate that might not exist in the input.
  • Compare before updating: only a strictly greater value improves the answer. Equal maxima need no special handling because we return a value, not an index.
  • Update one variable: assigning to largest changes our remembered answer, not the array.

Invoke the method

Place this main method in the same class as largestElement above, for example Main. Compile and run that class. The expected console output is 9.

Java
public static void main(String[] args) {
    // Use the same input as the explanation and walkthrough.
    int[] values = {4, 7, 2, 9, 3};
    System.out.println(largestElement(values)); // Prints 9.
}

Dry run

Numbered illustrated dry run for Find the Largest Element in an Array; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

Read each row alongside the Java loop. The index, comparison and value of largest show the state immediately after that instruction. No player or separate editor is needed.

Follow the Java loop

Here is the complete scan for [4, 7, 2, 9, 3]. Each decision corresponds to the comparison and assignment in the method above.

Index Value Decision Largest afterward
0 4 Initialize from the first element 4
1 7 7 > 4: update 7
2 2 2 > 7 is false: keep 7
3 9 9 > 7: update 9
4 3 3 > 9 is false: keep 9

All five values are covered. Return 9. There were four value comparisons after initialization.

Why the algorithm works

Our invariant is: after processing index i, largest is the maximum of values[0..i]. We can check this in three stages.

Initialization

The initial prefix contains only values[0]. Setting largest = values[0] gives the maximum of that one-element prefix. The invariant is true before the loop begins.

Maintenance

Assume largest is the maximum of the processed prefix. The next value is either greater, in which case it becomes the new maximum, or not greater, in which case the old maximum remains correct. Either way, extending the prefix by one element preserves the invariant.

Termination

The loop stops when the processed prefix is the whole array. The invariant then says that largest is the maximum of the entire input. A single-element array also works: the loop runs zero times and returns its only value.

Complexity and alternative approaches

Time: O(n). Initialization reads the first value; the loop performs exactly n−1 value comparisons. An unread element could be larger than everything seen, so inspecting every value is necessary in the worst case.

Extra space: O(1). largest and index are a fixed number of variables, regardless of the array length. The input array itself is not extra space.

Approach comparison

Approach Time Extra space Tradeoff
One-pass running maximum O(n) O(1) Preferred: simple, optimal, and preserves the input.
Sort a copy O(n log n) O(n) for the copy, plus sorting workspace Preserves the original order, but does unnecessary sorting.
Sort in place O(n log n) with a suitable comparison sort Depends on the sorting algorithm Changes the input order; violates this problem’s no-modification requirement.
Linear recursion O(n) O(n) call stack Same comparisons, but extra stack space and stack-overflow risk on large inputs.

Sorting and taking the final value finds the maximum too. However, a sort’s own auxiliary memory is algorithm-dependent: “in place” does not automatically mean zero stack or workspace. A recursive scan compares each value with the maximum of the remaining suffix; it trades a simple loop for n nested calls without reducing the work.

Common mistakes

  • Starting at zero: [-8, -3, -11, -5] would incorrectly return 0. Start with the first actual value.
  • Returning the index: for our default example, return 9, not 3.
  • Accessing index zero before checking input: the guard must run before values[0].
  • Sorting unnecessarily: it adds work and may change the caller’s array.
  • Stopping at the first improvement: 7 is better than 4, but the later 9 is larger. Finish the scan.

Practice next

Next lessonFind the Second Largest Element

Maintain two running answers instead of one.

Back to Arrays →