Leaders in an Array

Leaders in an Array is a clean little scanning problem. It looks like it needs nested loops, but a single backward pass solves it — the key is to scan in the direction that lets you reuse what you already know.

The slow way first

The literal definition suggests: for each element, loop over everything to its right and check that none is bigger. That works, but it is O(n²) — a nested loop for every position.

The question to ask: which direction should I scan so I do not have to re-look at the right side every time? If I walk from the right end toward the left, I can carry one number — the biggest value I have seen so far — and compare against it in O(1).

The idea: carry the running max

Scan right-to-left, keeping a variable maxSoFar = the largest value seen so far (everything to the right of the current index). For each element nums[i]:

• If nums[i] >= maxSoFar, then nothing to its right is bigger, so it is a leader. Record it and update maxSoFar = nums[i].
• Otherwise it is not a leader; skip it.

Because we collected leaders while walking backward, we reverse the result at the end to restore left-to-right order.

The whole trick is the scan direction: going right-to-left turns "is anything to my right bigger" into a single comparison against one carried number.

Walk through it

Step through the animation. The pointer i starts at the right end and moves left. The maxSoFar label updates each time we find a leader. Watch 2, then 5, then 17 get marked as leaders (they each meet or beat everything on their right), while 3, 4, and 16 are skipped because a bigger value sits to their right.

Pseudocode

result = empty list
maxSoFar = -infinity
for i from last index down to 0:
    if nums[i] >= maxSoFar:
        append nums[i] to result      # it is a leader
        maxSoFar = nums[i]            # raise the bar
reverse result                        # restore left-to-right order
return result

The Python solution

def leaders(nums):
    result = []
    max_so_far = float('-inf')
    for i in range(len(nums) - 1, -1, -1):
        if nums[i] >= max_so_far:
            result.append(nums[i])
            max_so_far = nums[i]
    result.reverse()
    return result

• result collects leaders as we find them (in right-to-left order for now).
• max_so_far starts at negative infinity so the rightmost element always qualifies.
• The range(len(nums) - 1, -1, -1) walks the indices backward, from the last to the first.
• Line 5 is the O(1) check — compare the current value against the one carried number instead of re-scanning the right side.
• When an element wins, we record it and raise max_so_far; then result.reverse() puts the answer back in left-to-right order.

Complexity

We use only a single extra variable (max_so_far), so the scan itself is O(1) extra space (the output list does not count against working space). One backward pass replaces the whole nested loop.

When this pattern shows up

Practice