Leaders in an Array
đź’» Try it yourself first. Write your solution in Java, C++, Python or JavaScript and run it against hidden tests, right here.On this page
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 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).
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}));
}
}#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
vector<int> leadersBrute(vector<int>& nums) {
int size = nums.size();
vector<int> leaders;
for (int scan = 0; scan < size; scan++) {
bool isLeader = true;
for (int right = scan + 1; right < size; right++) {
if (nums[right] >= nums[scan]) {
isLeader = false;
break;
}
}
if (isLeader) {
leaders.push_back(nums[scan]);
}
}
return leaders;
}
int main() {
vector<int> a = {4, 9, 2, 6, 3};
for (int x : leadersBrute(a)) {
cout << x << " ";
}
cout << "\n";
return 0;
}def leaders_brute(nums):
size = len(nums)
leaders = []
for scan in range(size):
is_leader = True
for right in range(scan + 1, size):
if nums[right] >= nums[scan]:
is_leader = False
break
if is_leader:
leaders.append(nums[scan])
return leaders
print(leaders_brute([4, 9, 2, 6, 3]))function leadersBrute(nums) {
const size = nums.length;
const leaders = [];
for (let scan = 0; scan < size; scan++) {
let isLeader = true;
for (let right = scan + 1; right < size; right++) {
if (nums[right] >= nums[scan]) {
isLeader = false;
break;
}
}
if (isLeader) {
leaders.push(nums[scan]);
}
}
return leaders;
}
console.log(leadersBrute([4, 9, 2, 6, 3]));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.
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}));
}
}#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
vector<int> findLeaders(vector<int>& nums) {
int size = nums.size();
vector<int> leaders;
int maxRight = nums[size - 1];
leaders.push_back(maxRight);
for (int scan = size - 2; scan >= 0; scan--) {
if (nums[scan] > maxRight) {
maxRight = nums[scan];
leaders.push_back(maxRight);
}
}
reverse(leaders.begin(), leaders.end());
return leaders;
}
int main() {
vector<int> a = {4, 9, 2, 6, 3};
for (int x : findLeaders(a)) {
cout << x << " ";
}
cout << "\n";
return 0;
}def find_leaders(nums):
size = len(nums)
max_right = nums[size - 1]
leaders = [max_right]
for scan in range(size - 2, -1, -1):
if nums[scan] > max_right:
max_right = nums[scan]
leaders.append(max_right)
leaders.reverse()
return leaders
print(find_leaders([4, 9, 2, 6, 3]))function findLeaders(nums) {
const size = nums.length;
const leaders = [];
let maxRight = nums[size - 1];
leaders.push(maxRight);
for (let scan = size - 2; scan >= 0; scan--) {
if (nums[scan] > maxRight) {
maxRight = nums[scan];
leaders.push(maxRight);
}
}
leaders.reverse();
return leaders;
}
console.log(findLeaders([4, 9, 2, 6, 3]));