Array Leaders

Right-to-left scan with a running maximum

time O(n)space O(1) beyond the output

Read left to right, each element needs the whole tail scanned to be judged, which is quadratic. Read RIGHT to left and the tail has already been seen, so one number — the largest value so far — decides every element on its own. The rightmost element is a leader by definition because its right side is empty. Moving left, an element is a leader exactly when it beats that running maximum, and when it does it becomes the new maximum, since it is now the biggest thing to the left of everything already processed. The comparison must be strict: a duplicate further right disqualifies an element even though the two are equal. Leaders come out in reverse order, so the list is flipped at the end.

Details

Animated on: nums = [12, 7, 19, 4, 19, 3, 9, 1]. An element is a leader when it is strictly greater than every element to its right. Answer: [19, 9, 1].

Problem:Array LeadersEasy

Right-to-left scan with a running maximum

step 1 / 9

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

The last element nums[7]=1 has nothing to its right, so it is a leader for free. Walking LEFT from here means the largest value seen so far already summarises the entire right side — that one number replaces the inner loop a left-to-right scan would need.

i=7· arr[7] = 1

Pseudocode

1FUNCTION leaders(nums)
2  out <- EMPTY LIST
3  maxRight <- nums[LENGTH(nums) - 1]
4  APPEND maxRight TO out
5  FOR i <- LENGTH(nums) - 2 DOWNTO 0
6    IF nums[i] > maxRight
7      APPEND nums[i] TO out
8      maxRight <- nums[i]
9  REVERSE out
10  RETURN out

← / → step · space play · Home restart

Every step in words

Show all 9 steps

The last element nums[7]=1 has nothing to its right, so it is a leader for free. Walking LEFT from here means the largest value seen so far already summarises the entire right side — that one number replaces the inner loop a left-to-right scan would need.
nums[6]=9 beats 1, the largest value anywhere to its right, so every element after it is smaller and nums[6]=9 is a leader. It also becomes the new bar to clear: maxRight <- 9. Leaders so far, right to left: [1, 9].
nums[5]=3 loses to 9 sitting at index 6 on its right, so it can never be a leader. Nothing to update — maxRight only ever grows as the scan moves left. Leaders so far, right to left: [1, 9].
nums[4]=19 beats 9, the largest value anywhere to its right, so every element after it is smaller and nums[4]=19 is a leader. It also becomes the new bar to clear: maxRight <- 19. Leaders so far, right to left: [1, 9, 19].
nums[3]=4 loses to 19 sitting at index 4 on its right, so it can never be a leader. Nothing to update — maxRight only ever grows as the scan moves left. Leaders so far, right to left: [1, 9, 19].
nums[2]=19 only TIES the running maximum 19 at index 4. A leader must be strictly greater than everything to its right, and an equal value to the right already fails that, so nums[2] is rejected and maxRight stays 19. Writing >= here is the classic wrong answer. Leaders so far, right to left: [1, 9, 19].
nums[1]=7 loses to 19 sitting at index 4 on its right, so it can never be a leader. Nothing to update — maxRight only ever grows as the scan moves left. Leaders so far, right to left: [1, 9, 19].
nums[0]=12 loses to 19 sitting at index 4 on its right, so it can never be a leader. Nothing to update — maxRight only ever grows as the scan moves left. Leaders so far, right to left: [1, 9, 19].
One pass over 8 elements is done. Reversing the collected list back into left-to-right order gives the leaders [19, 9, 1] at indices [4, 6, 7]. Comparing every element against everything on its right would have cost O(n^2); carrying one running maximum makes it O(n).

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Array Leaders in the editor All Arrays problems Back to roadmap