AlgoViz
HomeArrays & Hashing

Leaders in an Array

Medium

Scan from the right, keep the running max

Problem

Given an integer array nums, return a list of all the leaders in the array. A leader in an array is an element whose value is strictly greater than all elements to its right in the given array. The rightmost element is always a leader. The elements in the leader array must appear in the order they appear in the nums array.

In simple words

Scan from the right, keeping the max so far — anything at least that big is a leader.

The idea

An element is a leader when nothing to its right is larger, so sweeping right to left with a running maximum answers each element in O(1). Doing it left to right would need a fresh scan per element and cost O(n²).

The trick

  • The last element is always a leader.
  • Collect right to left, then reverse to restore the original order.
  • O(n) time, O(1) extra space beyond the output.
16
17
4
3
5
2
0
1
2
3
4
5

Step 1 of 8. Brute force: an element is a leader if it's ≥ everything to its right — check each. Values: 16, 17, 4, 3, 5, 2.

1/8
Brute force
timeO(n²)spaceO(1)

Check all to the right.

1for (let i = 0; i < n; i++) {2  let ok = true;3  for (let j = i + 1; j < n; j++) if (nums[j] > nums[i]) ok = false;4  if (ok) leaders.push(nums[i]);5}

Input

array
[16, 17, 4, 3, 5, 2]

Output

leaders
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [10, 22, 12, 3, 0, 6]
Output:
[22, 12, 6]
Explanation:
Each leader is >= everything to its right.

Example 2

Input:
nums = [5, 4, 3, 2, 1]
Output:
[5, 4, 3, 2, 1]
Explanation:
In a decreasing array everyone is a leader.

Example 3

Input:
nums = [1, 2, 3, 4]
Output:
[4]
Explanation:
Only the last, biggest element leads.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.