You are given an array arr of non-negative integers. Find all the leaders in the array.
An element is a leader if it is greater than or equal to every element to its right. The rightmost element is always a leader (there is nothing to its right to beat it).
Return the leaders in the same left-to-right order in which they appear in arr.
Input: arr = [16, 17, 4, 3, 5, 2] Output: [17, 5, 2] Nothing to the right of 17, 5, or 2 is larger than them.
Input: arr = [10, 4, 2, 4, 1] Output: [10, 4, 4, 1] Both 4s qualify — an equal element on the right still lets a value be a leader.
Input: arr = [5, 10, 20, 40] Output: [40] In a strictly increasing array, only the last element is a leader.
- 1 <= arr.size <= 10^6 - 0 <= arr[i] <= 10^6
Array Leaders is the friendliest member of the suffix-extreme family — the same right-to-left running-max idea that powers Stock Span, Next Greater Element, and Trapping Rain Water. The brute force asks "is anyone bigger to my right?" for each element; the optimal answers all of those at once with a single backward sweep.
Given an array arr, return all leaders — elements greater than or equal to every element to their right — in their original left-to-right order. The rightmost element is always a leader.
Worked example — arr = [16, 17, 4, 3, 5, 2]
sweep right → left, maxRight starts below any value 2 ≥ −∞ → leader, maxRight = 2 5 ≥ 2 → leader, maxRight = 5 3 < 5 → no 4 < 5 → no 17 ≥ 5 → leader, maxRight = 17 16 < 17 → no collected [2, 5, 17] → reverse → [17, 5, 2] ✓
“Is a leader defined with >= or strictly >?”
>= here — an equal element on the right still lets a value be a leader, which is why [10,4,2,4,1] keeps both 4s.
“Can the array contain 0 (or negatives)?”
Values start at 0, so seed the running max below any possible value (−∞ / INT_MIN), not 0, or the rightmost element might be wrongly rejected.
“Is the rightmost element always a leader?”
Yes — there's nothing to its right to beat it, so it seeds the answer.
“What about a strictly increasing array?”
Only the last element qualifies; everything before it is beaten by its right neighbour.
“What order should leaders come back in?”
Original left-to-right order. Collecting during a backward sweep gives reverse order, so reverse before returning.
“How large can the array be?”
Up to 10^6. That rules out the O(n²) check (~10^12 ops) — the single O(n) suffix-max sweep is required.
A couple of questions first.
Is "leader" greater-than-or-equal to everything on the right, so ties count?
Return them in original left-to-right order?
Given the size, I'll sweep right to left with a running max — O(n) time, O(1) space.
"Greater than or equal to every element on the right" is the same as "greater than or equal to the maximum of the elements on the right." Reducing a whole region to one number — its maximum — is what turns a per-element search into a single comparison.
Process the array backward, carrying maxRight = the largest value seen so far. When you reach index i, maxRight already summarizes everything to its right, so arr[i] >= maxRight decides leadership in O(1). One pass answers every element.
Because you discover leaders from the right, you append them in reverse of the required order. Reverse the collected list (or prepend as you go) so the output matches the original left-to-right order.
| Look right every time | Suffix max | |
|---|---|---|
| Idea | For each i, scan all elements to its right | One backward sweep with a running max |
| Time | O(n²) | O(n) |
| Space | O(1) | O(1) |
The full code for both is in the Approaches selector below.
Key takeaway
When a property depends on "everything to the right", precompute it as a suffix extreme: sweep right-to-left carrying a running maximum, and an element is a leader exactly when it meets that maximum. O(n) time, O(1) space — the same backward-running-max that solves Stock Span and Next Greater Element.
