Find Leaders in an Array in Java
Problem
A leader is an element that is strictly greater than every element to its right in the array — the last element is always a leader, since it has nothing to its right to beat.
Given an array of integers, find every element that is a leader.
Java Program
public class LeadersInArray {
public static void main(String[] args) {
int[] arr = {10, 25, 6, 3, 18, 4};
StringBuilder result = new StringBuilder();
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; // found something bigger or equal to the right, not a leader
}
}
if (isLeader) {
if (result.length() > 0) result.append(", ");
result.append(arr[i]);
}
}
System.out.println("Leaders: " + result);
}
}Output
Core Logic
Checking each element against every element that comes after it directly answers the question 'is everything to my right smaller than me?'.
- 1The outer loop picks a candidate index
i, assumed to be a leader until proven otherwise. - 2The inner loop checks every later index
j; if anyarr[j] >= arr[i]is found,iisn't a leader and the inner loopbreaks early. - 3An index that survives every comparison to its right is confirmed a leader and appended to the result.
- 4The last element always qualifies, since its inner loop never runs at all.
[10, 25, 6, 3, 18, 4], 25 beats everything after it, and so do 18 and 4 (the last element) — but 10 loses to 25, and 6 and 3 both lose to the later 18.Key Point: arr[j] >= arr[i], not just >, disqualifies a candidate — an equal value later in the array means the earlier one isn't strictly greater than everything to its right.
Why: Every element is checked against every element to its right, and the result can hold up to n leaders in the worst case.
Key Concepts
Approach 2: Optimized (Right-to-Left Scan)
public class LeadersInArrayOptimized {
public static void main(String[] args) {
int[] arr = {10, 25, 6, 3, 18, 4};
int[] leaders = new int[arr.length];
int count = 0;
int maxFromRight = arr[arr.length - 1]; // the last element is always a leader
leaders[count++] = maxFromRight;
for (int i = arr.length - 2; i >= 0; i--) {
if (arr[i] > maxFromRight) { // beats everything seen so far from the right
maxFromRight = arr[i];
leaders[count++] = maxFromRight;
}
}
StringBuilder result = new StringBuilder();
for (int i = count - 1; i >= 0; i--) { // walk backward to restore left-to-right order
if (result.length() > 0) result.append(", ");
result.append(leaders[i]);
}
System.out.println("Leaders: " + result);
}
}
Output
Core Logic
Scanning from the right while tracking the largest value seen so far means every element only needs one comparison against that running maximum, not against every element to its right individually.
- 1The scan starts from the last element, which is automatically a leader and becomes the first
maxFromRight. - 2Moving leftward, any element greater than the current
maxFromRightis a leader — everything to its right is, by definition, at mostmaxFromRight. - 3Each newly found leader updates
maxFromRight, since it's now the value every earlier element must beat. - 4Leaders are collected in right-to-left order during the scan, then reversed when printed to match the array's original left-to-right order.
[10, 25, 6, 3, 18, 4] from the right, maxFromRight updates through 4, then 18, then 25 — collecting leaders 4, 18, 25 in that order, printed back as 25, 18, 4.Key Point: This checks each element only once against a single running value, instead of the brute-force version's repeated re-scanning of everything to the right — the same running-maximum idea used to find the maximum difference between two elements.
Why: A single backward pass tracks one running maximum, and the leaders collected along the way can still total up to n in the worst case.