Leaders in an Array

+10

You get an array of integers nums. An element is a leader when it is greater than or equal to every element to its right. The last element has nothing to its right, so it is always a leader. Return every leader, in the order they appear in nums from left to right.

Function

leaders(nums: integer-array) → integer-array

numsinteger-array: the array of integers to search
Returnsinteger-array: the leaders of nums, from left to right

Constraints

1 ≤ nums.length ≤ 25000
-10⁹ ≤ nums[i] ≤ 10⁹

Examples

Input: nums = [12, 5, 9, 3, 6, 2]
Output: [12, 9, 6, 2]
Explanation: 2 is last, so it leads. 6 beats the 2 after it, 9 beats 3, 6 and 2, and 12 beats everything. 5 loses to 9 and 3 loses to 6, so the answer is [12, 9, 6, 2].

Follow-up

If the values arrive one at a time and after each you must report the leaders so far, how do you update the list in O(1) amortized time per value?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Read from the left, every element needs a fresh scan of its suffix. Walk from the right instead: the only thing you need to know about the suffix is its largest value, and one variable holds it. That turns an O(n²) check into a single pass.

Check everything to the right

Correct, but does not finish on the largest tests

Intuition

Apply the definition: for each index i, scan the later elements and stop at the first one strictly greater than nums[i]. If the scan reaches the end, nums[i] leads. You test indices left to right, so the leaders come out in order. In [12, 5, 9, 3, 6, 2], 5 stops at 9 and 3 stops at 6.

The cost is in the scans that run to the end. In 24,999 equal values followed by one larger value, every element walks almost the whole array: about 25,000 × 25,000 / 2, over 3 × 10^8 comparisons.

Algorithm

Create an empty result list.
For each index i, scan j from i + 1 to the end.
If some nums[j] is greater than nums[i], stop: nums[i] is not a leader.
If no such j exists, append nums[i] to the result.
Return the result.

def leaders(nums):
    n = len(nums)
    result = []
    for i in range(n):
        is_leader = True
        for j in range(i + 1, n):
            if nums[j] > nums[i]:  # a bigger value on the right rules it out
                is_leader = False
                break
        if is_leader:
            result.append(nums[i])
    return result

One pass from the right with a running maximum

Intuition

Being at least as large as every element on the right is the same as being at least as large as their maximum. Walking right to left, you can keep that maximum up to date. The last element leads and starts the maximum. Each element to its left leads when it is at least the maximum, and then becomes the new maximum; otherwise a larger value sits to its right.

On [12, 5, 9, 3, 6, 2]: 2 leads, then 6, then 9, then 12, while 3 and 5 fall below the maximum. You found [2, 6, 9, 12]; reversed, that is the answer.

Each element is compared once: O(n) time and O(1) extra space besides the result. The R version marks leaders in a logical(n) vector, so its extra space is O(n).

Algorithm

Put the last element in the result and set best to it.
Move i from the second to last index down to 0.
If nums[i] ≥ best, append nums[i] to the result and set best to it.
Reverse the result so the leaders read left to right, and return it.

def leaders(nums):
    n = len(nums)
    best = nums[n - 1]  # the largest value to the right of the current index
    found = [best]      # the last element is always a leader
    for i in range(n - 2, -1, -1):
        if nums[i] >= best:
            best = nums[i]
            found.append(nums[i])
    found.reverse()  # collected right to left, returned left to right
    return found

Pitfalls and edge cases

Using > instead of ≥ against the running maximum. In [4, 7, 7, 1, 7] every 7 leads, but a strict comparison keeps only the last one.
Starting the maximum at 0 instead of at the last element. [-1, -5] must return both, but a maximum of 0 rules them out.
Returning the leaders in the order you found them, [2, 6, 9, 12] instead of [12, 9, 6, 2].
Adding the last element twice by starting the loop at the last index after already putting it in the result.
Comparing each element only with its neighbour. In [5, 3, 9], 5 beats the 3 next to it, but the 9 means the answer is [9].

Frequently asked questions3

What is the time complexity of finding leaders in an array?

O(n) with one pass from the right, because each element is compared once with the running maximum. Checking every element against everything to its right costs O(n²) in the worst case, for example when all values are equal.

Is the last element always a leader?

Yes. A leader must be at least as large as every element to its right, and the last element has none, so the condition holds with nothing to check.

Do equal values count as leaders?

Here, yes: a leader must be greater than or equal to every element on its right, so in [4, 7, 7, 1, 7] all three 7s lead. Some versions ask for strictly greater; then compare with >, and only the last of the tied values leads.

def leaders(nums):
    # Write code here

Test #1

Test #2

Test #3

Argument

nums = [12, 5, 9, 3, 6, 2]

Expected Output

[12, 9, 6, 2]