Topics › Arrays › Medium

Leaders in an Array

Medium TUF ID 30 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

An element of an array is a leader if it is strictly greater than every element to its right. The last element has nothing to its right, so it is always a leader. Return all leaders in the order they appear in the array.

Constraints: 0 ≤ n ≤ 10^5, values fit in a 32-bit signed integer (negative values allowed). Some versions use “greater than or equal to”; this article uses the strict version, which is the one on the sheet, and points out the one-character change needed for the other.

Example 1

nums = [10, 22, 12, 3, 0, 6]
answer = [22, 12, 6]     // 22 beats 12, 3, 0, 6; 12 beats 3, 0, 6; 6 is last

Example 2

nums = [16, 17, 4, 3, 5, 2]
answer = [17, 5, 2]      // 16 is not a leader because 17 is to its right

Example 3

nums = [3, 3, 3]
answer = [3]             // equal values do not count as "strictly greater", so only the last one

Approach 1: Brute force

Intuition. The definition is a statement about every element to the right, so the direct approach checks it literally: for each index i, scan i + 1 .. n - 1 and see whether any value is >= nums[i]. If none is, nums[i] is a leader. Collecting leaders while i moves left to right produces them in the required order with no extra work.

Algorithm.

1. For each index i from 0 to n - 1:
2. Assume nums[i] is a leader. For each j from i + 1 to n - 1, if nums[j] >= nums[i], it is not; stop the inner scan.
3. If the assumption survived, append nums[i] to the answer.

static List<Integer> bruteForce(int[] nums) {
    int n = nums.length;
    List<Integer> leaders = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        boolean leader = true;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] >= nums[i]) {            // something to the right is at least as big
                leader = false;
                break;
            }
        }
        if (leader) leaders.add(nums[i]);
    }
    return leaders;
}

Complexity. Time O(n^2): in the worst case (a strictly decreasing array, where every element is a leader) the inner loop never breaks early, giving n(n-1)/2 comparisons. Space O(1) beyond the output list.

The break helps on inputs where a bigger value appears soon, but it does not change the worst case. For n = 10^5 the quadratic scan is too slow.

Approach 2: Optimal, scan from the right with a running maximum

Intuition. “Greater than everything to its right” is really “greater than the maximum of everything to its right”. That maximum is a quantity we can maintain cheaply if we walk the array from right to left: after processing index i + 1 .. n - 1, we know the largest value among them, call it maxRight. Then nums[i] is a leader exactly when nums[i] > maxRight, and whether it is a leader or not, the new suffix maximum is max(maxRight, nums[i]). In fact, when nums[i] is a leader it is the new maximum, and when it is not, the maximum does not change. So the update is just “if leader, set maxRight = nums[i]”.

The leaders are discovered right to left, so the collected list is in reverse order. One Collections.reverse fixes that.

Algorithm.

1. If the array is empty, return an empty list.
2. Set maxRight = nums[n - 1] and add it to the list (the last element is always a leader).
3. For i from n - 2 down to 0: if nums[i] > maxRight, add nums[i] and set maxRight = nums[i].
4. Reverse the list and return it.

static List<Integer> optimal(int[] nums) {
    int n = nums.length;
    List<Integer> leaders = new ArrayList<>();
    if (n == 0) return leaders;
    int maxRight = nums[n - 1];
    leaders.add(maxRight);                       // the last element has nothing to its right
    for (int i = n - 2; i >= 0; i--) {
        if (nums[i] > maxRight) {
            leaders.add(nums[i]);
            maxRight = nums[i];
        }
    }
    Collections.reverse(leaders);                // collected right to left; restore left-to-right order
    return leaders;
}

Dry run on nums = [10, 22, 12, 3, 0, 6]:

After reversing: [22, 12, 6].

Complexity. Time O(n): one pass plus a reverse of at most n elements. Space O(1) beyond the output list.

Why does the running maximum make the check exact rather than approximate? Because the only information about the suffix that matters to the definition is its maximum. If nums[i] beats the maximum it beats every element; if it does not beat the maximum, the maximum itself is a witness that nums[i] is not a leader.

Edge cases and pitfalls

• Empty array. Return an empty list. The optimal method guards n == 0 before reading nums[n - 1].
• Single element. It is the only leader: [7] -> [7].
• Strictly increasing array. Only the last element is a leader: [1, 2, 3, 4, 5] -> [5].
• Strictly decreasing array. Every element is a leader; this is the worst case for the brute force.
• Equal values. With the strict definition, [3, 3, 3] gives [3]. For the non-strict variant (“greater than or equal”), change >= to > in the brute force and > to >= in the optimal method, and [3, 3, 3] becomes [3, 3, 3].
• Sentinel initialisation. A tempting shortcut is maxRight = Integer.MIN_VALUE and a single loop from n - 1. That silently drops a last element equal to Integer.MIN_VALUE, because MIN_VALUE > MIN_VALUE is false. Seeding maxRight with the actual last element avoids the bug, and the test [MIN_VALUE, MIN_VALUE] -> [MIN_VALUE] would catch the shortcut.
• Output order. The right-to-left scan collects leaders in reverse. Forgetting the final reverse yields [6, 12, 22] for example 1, which is wrong.
• Negative numbers. Comparisons behave the same; [-1, -5, -2, -9] -> [-1, -2, -9].

Related problems

• Next Permutation also scans from the right, looking for the first place where a suffix property (non-increasing) breaks.
• Rearrange array elements by sign is the previous problem in this section.
• Longest Consecutive Sequence in an Array is the next one.