Pattern visualizer
Leaders in an Array
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. 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]..
Right-to-left scan with a running maximum
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.
1FUNCTION leaders(nums)2 out <- EMPTY LIST3 maxRight <- nums[LENGTH(nums) - 1]4 APPEND maxRight TO out5 FOR i <- LENGTH(nums) - 2 DOWNTO 06 IF nums[i] > maxRight7 APPEND nums[i] TO out8 maxRight <- nums[i]9 REVERSE out10 RETURN out
← / → step · space play · Home restart