Leaders in an Array — Solution in Python, Java & C++
Leaders in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays.
Leaders in an Array is an easy coding problem on arrays, asked in Amazon, TCS and Accenture interviews.
- Difficulty: Easy
- Topics: Arrays
- Asked at: Amazon, TCS, Accenture
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An element of arr is a leader if it is greater than or equal to every element to its right. The rightmost element is always a leader.
Return all leaders in the order they appear in the array (left to right).
Example 1
Input: arr = [16,17,4,3,5,2]
Output: [17,5,2]
Explanation: 17 beats everything to its right, 5 beats {2}, and 2 is last.
Example 2
Input: arr = [1,2,3,4,0]
Output: [4,0]
Example 3
Input: arr = [7,7,7]
Output: [7,7,7]
Explanation: Ties count — the comparison is >=.
Constraints
1 <= arr.length <= 10000 <= arr[i] <= 100000
Hints for Leaders in an Array
Hint 1
Comparing every element with all elements to its right is O(n²). What information does a right-to-left scan give you for free?
Hint 2
Walking backwards, the maximum of everything seen so far is the maximum of the suffix.
Hint 3
Collect leaders while scanning backwards, then reverse to restore the original order.
How to solve Leaders in an Array
A leader is an element that ties or beats the maximum of its suffix. Scanning right to left makes that suffix maximum a single running variable.
Approach
- Walk
ifromn - 1down to0, carryingbest— the maximum ofarr[i+1..n-1]. - If
arr[i] >= best, recordarr[i]as a leader and updatebest = arr[i]. - Reverse the collected list so it reads left to right.
Why it works
By induction, when index i is examined best already equals the suffix maximum, which is precisely the quantity the definition compares against. The last element trivially qualifies because its suffix is empty.
Complexity
- Time —
O(n) - Space —
O(n) for the output
Pitfalls
- Using
>instead of>=drops duplicate leaders such as[7,7,7]. - Forgetting the final reverse yields the leaders in right-to-left order.
Reference solution
Python
from typing import List
def leaders(arr: List[int]) -> List[int]:
out = []
best = -1
for i in range(len(arr) - 1, -1, -1):
if arr[i] >= best:
out.append(arr[i])
best = arr[i]
out.reverse()
return outJava
public static int[] leaders(int[] arr) {
int n = arr.length;
int[] tmp = new int[n];
int m = 0;
int best = -1;
for (int i = n - 1; i >= 0; i--) {
if (arr[i] >= best) {
tmp[m++] = arr[i];
best = arr[i];
}
}
int[] out = new int[m];
for (int i = 0; i < m; i++) out[i] = tmp[m - 1 - i];
return out;
}C++
vector<int> leaders(vector<int>& arr) {
vector<int> out;
int best = -1;
for (int i = (int) arr.size() - 1; i >= 0; i--) {
if (arr[i] >= best) {
out.push_back(arr[i]);
best = arr[i];
}
}
reverse(out.begin(), out.end());
return out;
}JavaScript
var leaders = function(arr) {
const out = [];
let best = -1;
for (let i = arr.length - 1; i >= 0; i--) {
if (arr[i] >= best) {
out.push(arr[i]);
best = arr[i];
}
}
out.reverse();
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays