Leaders in an Array
Leaders in an Array: an element is a leader if it is greater than or equal to every element to its right. Return all leaders in the order they appear.
- 1 <= n <= 10⁵
- 1 <= nums[i] <= 10⁹
- The rightmost element is always a leader
Intuition
Leaders in an array finds every element greater than all elements to its right. The rightmost element is always a leader, since nothing follows it.
The direct reading — for each element, scan everything after it — is O(n²) and recomputes the same information repeatedly.
Scanning right to left removes that redundancy:
- Walking backwards, the maximum of everything already seen is exactly the maximum of everything to the element's right — one variable replaces the inner loop.
So the algorithm keeps a running maximum, starting from the last element. At each position, compare the element against that maximum: if it is greater, it is a leader, and the maximum updates.
The comparison must be strictly greater. The definition requires exceeding everything to the right, so an element equal to the current maximum is not a leader. Using >= wrongly admits duplicates — in [5, 5, 3], only the second 5 and the 3 qualify, not the first 5.
The last element is handled without a special case by initialising the maximum to negative infinity, which anything exceeds.
Leaders are discovered in reverse order, so the collected list must be reversed before returning if the problem expects left-to-right order — a step easy to omit since the values themselves are correct.
The running maximum only ever grows, which means the leaders form a non-increasing sequence when read left to right. That is a useful sanity check on any implementation.
Scanning right-to-left turns a quadratic question into a linear one: a leader must beat everything to its right, and walking backwards means "everything to the right" is a single running maximum. Whenever an element's status depends on all elements on one side, sweep from that side and carry the aggregate.
Approach
Before reading on: price up what the direct approach costs here, then ask what you would need to remember from the left to avoid re-scanning. Aim for O(n) time and O(1) space.
Scan from the right
Walking backwards, the maximum of everything seen so far is exactly the maximum to the element's right — one variable replaces the entire inner loop.
Track a running maximum
Initialise to negative infinity so the last element always qualifies, then update as larger values appear. No special case for the rightmost element is needed.
Compare strictly
Use >, not >=. A leader must exceed everything to its right, so in [5, 5, 3] the first 5 does not qualify — >= wrongly admits it.
Update only on a leader
The maximum changes exactly when a leader is found, since only a larger element can raise it. Non-leaders leave it untouched.
Reverse before returning
Leaders are collected in reverse order. Reverse the list if left-to-right output is expected — the values are right but the order is not.
Sanity-check the result
Because the running maximum only grows, the leaders form a non-increasing sequence read left to right. Any other shape signals a bug.
Cost of the scan
One backward pass with a single variable gives O(n) time and O(1) space beyond the output, improving on the O(n²) direct reading.
Solution & live demo
Common pitfalls
Rescanning the suffix for every element
for i in range(len(nums)):
if all(nums[i] >= nums[j] for j in range(i + 1, len(nums))):
res.append(nums[i])for v in reversed(nums):
if v >= maxRight:
res.append(v); maxRight = vThat's O(n²) and recomputes the same suffix maximum repeatedly. Sweeping backwards keeps it in one variable, so each element is examined once.
Using strict > for the comparison
if v > maxRight:
if v >= maxRight:
GFG defines a leader as greater than or equal to everything on its right, so on [7, 4, 5, 7, 3] both sevens qualify. Strict > drops the first one and returns an answer one element short.
Forgetting to reverse the collected result
return res
res.reverse() return res
Collecting while walking backwards produces the leaders in reverse positional order. The expected output preserves their original left-to-right order.
Edge cases
It is trivially a leader.
Only the last element is a leader.
Every element is a leader.
The >= comparison includes them all, which is what the definition asks for — using > drops the earlier copies.