.png)
Leaders in an Array
Problem Statement
Given an array of integers, find all the leaders in the array.
An element is called a leader if it is greater than or equal to all the elements to its right side.
The rightmost element is always a leader.
Example 1
Input
arr = [16, 17, 4, 3, 5, 2]
Output
17 5 2
Explanation
- 17 is greater than all elements to its right
- 5 is greater than 2
- 2 is the last element
Example 2
Input
arr = [7, 10, 4, 10, 6, 5, 2]
Output
10 10 6 5 2
Why This Problem Is Important
- Common interview question
- Tests:
- Array traversal
- Comparison logic
- Right-to-left scanning
- Forms the base for:
- Suffix maximum problems
- Stock buy-sell variants
- Monotonic patterns
Approaches Overview
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force | O(n²) | O(1) |
| Optimized (Right Scan) | O(n) | O(1) |
Approach 1: Brute Force Method
Idea
For each element, check all elements to its right.
If no element on the right is greater, then the current element is a leader.
Algorithm
- Traverse array from index 0 to n-1
- Assume arr[i] is a leader
- Compare it with all elements to the right
- If any element is greater, it is not a leader
- Print all valid leaders
Time and Space Complexity
- Time Complexity: O(n²)
- Space Complexity: O(1)
C Implementation
#include<stdio.h>
int main() {
int arr[] = {16, 17, 4, 3, 5, 2};
int n = 6;
for(int i = 0; i < n; i++) {
int isLeader = 1;
for(int j = i + 1; j < n; j++) {
if(arr[j] > arr[i]) {
isLeader = 0;
break;
}
}
if(isLeader)
printf("%d ", arr[i]);
}
return 0;
}
Output
17 5 2
C++ Implementation
#include<iostream>
using namespace std;
int main() {
int arr[] = {16, 17, 4, 3, 5, 2};
int n = 6;
for(int i = 0; i < n; i++) {
bool isLeader = true;
for(int j = i + 1; j < n; j++) {
if(arr[j] > arr[i]) {
isLeader = false;
break;
}
}
if(isLeader)
cout << arr[i] << " ";
}
return 0;
}
Java Implementation
public class LeadersBruteForce {
public static void main(String[] args) {
int[] arr = {16, 17, 4, 3, 5, 2};
for(int i = 0; i < arr.length; i++) {
boolean isLeader = true;
for(int j = i + 1; j < arr.length; j++) {
if(arr[j] > arr[i]) {
isLeader = false;
break;
}
}
if(isLeader)
System.out.print(arr[i] + " ");
}
}
}
Python Implementation
arr = [16, 17, 4, 3, 5, 2]
n = len(arr)
for i in range(n):
is_leader = True
for j in range(i + 1, n):
if arr[j] > arr[i]:
is_leader = False
break
if is_leader:
print(arr[i], end=" ")
JavaScript Implementation
let arr = [16, 17, 4, 3, 5, 2];
let n = arr.length;
for (let i = 0; i < n; i++) {
let isLeader = true;
for (let j = i + 1; j < n; j++) {
if (arr[j] > arr[i]) {
isLeader = false;
break;
}
}
if (isLeader)
process.stdout.write(arr[i] + " ");
}
.
Approach 2: Optimized Method (Right-to-Left Traversal)
Idea
- Traverse the array from right to left
- Keep track of the maximum element seen so far
- If the current element is greater than or equal to this maximum, it is a leader
Algorithm
- Initialize maxRight = arr[n-1]
- Add maxRight to result
- Traverse from index n-2 to 0
- If arr[i] >= maxRight:
- Update maxRight
- Add element to result
- Reverse result for correct order
Time and Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(1) (excluding output list)
C Implementation
#include<stdio.h>
int main() {
int arr[] = {16, 17, 4, 3, 5, 2};
int n = 6;
int maxRight = arr[n - 1];
int leaders[6], k = 0;
leaders[k++] = maxRight;
for(int i = n - 2; i >= 0; i--) {
if(arr[i] >= maxRight) {
maxRight = arr[i];
leaders[k++] = arr[i];
}
}
for(int i = k - 1; i >= 0; i--)
printf("%d ", leaders[i]);
return 0;
}
C++ Implementation
#include<iostream>
#include<vector>
using namespace std;
int main() {
int arr[] = {16, 17, 4, 3, 5, 2};
int n = 6;
vector leaders;
int maxRight = arr[n - 1];
leaders.push_back(maxRight);
for(int i = n - 2; i >= 0; i--) {
if(arr[i] >= maxRight) {
maxRight = arr[i];
leaders.push_back(arr[i]);
}
}
for(int i = leaders.size() - 1; i >= 0; i--)
cout << leaders[i] << " ";
return 0;
}
Java Implementation
import java.util.*;
public class LeadersOptimized {
public static void main(String[] args) {
int[] arr = {16, 17, 4, 3, 5, 2};
List leaders = new ArrayList<>();
int maxRight = arr[arr.length - 1];
leaders.add(maxRight);
for(int i = arr.length - 2; i >= 0; i--) {
if(arr[i] >= maxRight) {
maxRight = arr[i];
leaders.add(arr[i]);
}
}
Collections.reverse(leaders);
for(int num : leaders)
System.out.print(num + " ");
}
}
Python Implementation
arr = [16, 17, 4, 3, 5, 2]
leaders = []
max_right = arr[-1]
leaders.append(max_right)
for i in range(len(arr) - 2, -1, -1):
if arr[i] >= max_right:
max_right = arr[i]
leaders.append(arr[i])
leaders.reverse()
print(*leaders)
JavaScript Implementation
let arr = [16, 17, 4, 3, 5, 2];
let n = arr.length;
let leaders = [];
let maxRight = arr[n - 1];
leaders.push(maxRight);
for (let i = n - 2; i >= 0; i--) {
if (arr[i] >= maxRight) {
maxRight = arr[i];
leaders.push(arr[i]);
}
}
leaders.reverse();
console.log(leaders.join(" "));
Dry Run (Optimized Approach)
Array: [16, 17, 4, 3, 5, 2]
Start from right:
max = 2 → leader
5 > 2 → leader
17 > 5 → leader
Final leaders: 17 5 2
Summary
- Leaders are elements greater than all elements to their right
- Brute force is simple but inefficient
- Optimized approach is preferred in interviews
- Right-to-left traversal reduces time complexity to O(n)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
