LearnWithKiriti

Leaders in an Array

Easy GitHub ↗
đź’» Try it yourself first. Write your solution in Java, C++, Python or JavaScript and run it against hidden tests, right here.
Play
On this page
  1. Revision notes
  2. Brute
  3. Optimal

Revision notes

Leaders in an Array (interview style)

Video: “Leaders in an Array: 8 Minutes vs 1 Millisecond” on LearnWithKiriti (Kodee and Mr. Tock). Arrays series, episode 10.

An element is a leader if it is strictly greater than every element to its right. The last element is always a leader. Return the leaders left to right. Example: [4, 9, 2, 6, 3] -> [9, 6, 3]. Strict means equals do not count: [7, 4, 7, 5, 3] -> [7, 5, 3]. Related: LeetCode 1299, Replace Elements with Greatest Element on Right Side (same right-to-left scan).

Folder Approach Time Extra space
Brute/ For each number, look right; stop at the first number that is bigger or equal O(n^2), worst case a strictly decreasing list O(1)
Optimal/ Scan right to left carrying maxRight; collect, reverse once O(n) O(1) (the answer list is not counted)

A million numbers at about a billion steps a second: brute force worst case about 500 billion checks (about 8 minutes); one pass about 1 million steps (about 1 millisecond), roughly 500,000 times faster.

Rebuild it

Start at the right. Carry the max. The inner loop of the brute force keeps asking “what is the biggest thing on my right?”. Remember the answer (maxRight) instead of asking again. A number that beats maxRight beats everything on its right. The scan finds leaders backwards, so reverse once (no sorting needed: leaders are already in decreasing order).

Shortcut that fails: “just the biggest number and the last one” gives [10, 1] for [10, 2, 8, 3, 1]; the real answer is [10, 8, 3, 1].

See Brute/pseudocode.md and Optimal/pseudocode.md. Every program was compiled, run and random-tested against a naive oracle.

brute

Brute

Brute force

leaders = []
for scan from 0 to size - 1:
    isLeader = true
    for right from scan + 1 to size - 1:
        if nums[right] >= nums[scan]:
            isLeader = false
            break
    if isLeader:
        leaders.add(nums[scan])
return leaders

Dry run on [4, 9, 2, 6, 3] (6 checks in total):

  • scan 4: right sees 9, bigger, break. Loses.
  • scan 9: right checks 2, 6, 3. No break. Leader.
  • scan 2: right sees 6, break. Loses.
  • scan 6: right sees 3. Leader.
  • scan 3: nothing to the right. Leader.

Result [9, 6, 3].

Time: worst case a strictly decreasing list, n(n - 1) / 2 checks = O(n^2). A million numbers: 499,999,500,000 checks, about 8 minutes. Extra space: O(1).

LeadersBrute.java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class LeadersBrute {
    static List<Integer> leadersBrute(int[] nums) {
        int size = nums.length;
        List<Integer> leaders = new ArrayList<>();
        for (int scan = 0; scan < size; scan++) {
            boolean isLeader = true;
            for (int right = scan + 1; right < size; right++) {
                if (nums[right] >= nums[scan]) {
                    isLeader = false;
                    break;
                }
            }
            if (isLeader) {
                leaders.add(nums[scan]);
            }
        }
        return leaders;
    }

    public static void main(String[] args) {
        System.out.println(leadersBrute(new int[]{4, 9, 2, 6, 3}));
        System.out.println(leadersBrute(new int[]{10, 2, 8, 3, 1}));
    }
}
optimal

Optimal

Optimal: right to left, carry maxRight

maxRight = nums[size - 1]
leaders = [maxRight]
for scan from size - 2 down to 0:
    if nums[scan] > maxRight:
        maxRight = nums[scan]
        leaders.add(maxRight)
reverse(leaders)
return leaders

Dry run on [4, 9, 2, 6, 3] (maxRight starts at 3, leaders [3]):

scan value beats maxRight? maxRight leaders
3 6 yes 6 [3, 6]
2 2 no 6 [3, 6]
1 9 yes 9 [3, 6, 9]
0 4 no 9 [3, 6, 9]

Reverse -> [9, 6, 3].

Time: one pass, O(n). A million numbers: about 1 million steps, about 1 millisecond. Extra space: O(1) (the output is the answer). Seeding maxRight with nums[size - 1] (not a minimum value) stays correct even if the array holds the smallest possible integer. Assumes the array has at least one number.

Edge cases: one number -> itself. All equal -> only the last. Strictly decreasing -> everyone. Strictly increasing -> only the last.

LeadersOptimal.java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class LeadersOptimal {
    static List<Integer> findLeaders(int[] nums) {
        int size = nums.length;
        List<Integer> leaders = new ArrayList<>();
        int maxRight = nums[size - 1];
        leaders.add(maxRight);
        for (int scan = size - 2; scan >= 0; scan--) {
            if (nums[scan] > maxRight) {
                maxRight = nums[scan];
                leaders.add(maxRight);
            }
        }
        Collections.reverse(leaders);
        return leaders;
    }

    public static void main(String[] args) {
        System.out.println(findLeaders(new int[]{4, 9, 2, 6, 3}));
        System.out.println(findLeaders(new int[]{10, 2, 8, 3, 1}));
    }
}