Given an array arr of integers, find and return the largest element in it.
The array always has at least one element, so an answer is guaranteed to exist. Values may repeat — if the maximum appears more than once, you still return that single value.
arr = [5, 5, 5, 5] returns 5 — duplicates of the maximum don't change the answer.arr[0] is always a real element, so the answer is correct even for arrays of all zeros or (in the general case) all negatives. Seeding with 0 would silently break on negative inputs.largest and secondLargest, updating both in a single pass — and be careful to push the old largest down into secondLargest when a new champion appears.k for an O(n log k) scan, or Quickselect to partition around the k-th order statistic in O(n) average time.n-1 comparisons in the worst case — think of a knockout tournament: each game eliminates one loser, and n-1 losers must be eliminated to leave one winner.max() built-ins, streaming analytics, and the reduce/fold operation in functional programming.Input: arr = [1, 8, 7, 56, 90] Output: 90 The largest element of the array is 90.
Input: arr = [5, 5, 5, 5] Output: 5 Every element is 5, so the largest is 5.
Input: arr = [10] Output: 10 A single element is trivially the largest.
- 1 <= arr.size <= 10^6 - 0 <= arr[i] <= 10^6
Finding the largest element is the first "sweep the array once and keep the best" pattern — the seed of running-aggregate thinking you'll reuse for min, sum, count, and second-largest. The brute force sorts; the optimal keeps a running maximum. Let's build up why one pass is provably the best you can do.
O(n log n)) does strictly more work than a single O(n) scan.Given an array arr, return its largest value. The array has at least one element, so an answer always exists. Values may repeat, and the maximum may appear more than once — you still return that single value.
Worked example — arr = [1, 8, 7, 56, 90]
see 1 → best = 1 see 8 → 8 > 1 → best = 8 see 7 → 7 < 8 → best = 8 see 56 → 56 > 8 → best = 56 see 90 → 90 > 56 → best = 90 ✓
A few sharp questions before coding surface the edge cases that decide your loop's details.
“Is the array guaranteed non-empty?”
Here yes, at least one element. If not, you'd have to decide what "largest of nothing" even returns.
“Can the values be negative?”
Not in this problem (values are zero or more), but always worth asking — it decides whether you may seed your running max with 0.
“Can the maximum appear more than once?”
Yes. You return the value itself; duplicates of the maximum don't change the answer.
“What about a single-element array?”
That element is trivially the largest.
“Do I return the value or its index?”
The value. Worth confirming, since a running-max can just as easily track the index.
“How large can the array be?”
Up to 10^6. Both an O(n log n) sort and an O(n) scan finish in time, but the scan avoids the sort's overhead entirely.
A couple of quick checks before I code.
Is the array always non-empty?
Can the values be negative, or are they all non-negative?
Should I return the largest value itself, not its index?
Good. I'll do a single linear pass, tracking the maximum seen so far.
Sorting arranges every element relative to every other, but the question is about one element: the maximum. All that ordering is wasted effort. Carrying a single "best so far" value answers the question directly, in one sweep.
You cannot name the maximum without having looked at every element — skip one and it might have been the largest. So any correct solution must read all n values at least once. A single O(n) scan hits that lower bound exactly, so you can't do asymptotically better.
Initialize the running maximum to arr[0] — a real element — not to 0. It happens to work here because values are non-negative, but the moment negatives are allowed, seeding with 0 silently returns 0 for an all-negative array. Seeding with arr[0] is always safe.
| Sort & take last | Running maximum | |
|---|---|---|
| Idea | Fully order, read the end | One sweep, keep the best |
| Time | O(n log n) | O(n) |
| Space | O(1) | O(1) |
The full code for both is in the Approaches selector below.
Key takeaway
To find a single extreme — max, min, or similar — carry one running value and update it in a single O(n) sweep. Sorting would answer the question too, but it pays O(n log n) to order elements you never needed ordered. Since you must inspect every element at least once, the linear scan is as good as it gets.