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
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.
Example 2 All negative
- Input
[-8, -3, -11, -5]- Output
-3
Rejects an unsafe initial answer of zero.
Example 3 Single value
- Input
[7]- Output
7
Checks the smallest valid array.
Example 4 Repeated maximum
- Input
[4, 9, 2, 9]- Output
9
Confirms duplicates do not change the result.
Hints Optional
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
- Reject
nullor empty input before accessing the first element. - Set
largesttovalues[0]. A real array value is a safe starting answer, including for an all-negative array. - Start
indexat1, because index0has already been processed. - If
values[index] > largest, replacelargest. Otherwise, keep it. - 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.
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 from0would 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
largestchanges 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.
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

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 return0. Start with the first actual value. - Returning the index: for our default example, return
9, not3. - 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:
7is better than4, but the later9is larger. Finish the scan.
Practice next
Next lessonFind the Second Largest ElementMaintain two running answers instead of one.