Question 7
Back to Exercise
Print all "leaders" of an array – elements greater than every element to their right – in their original order, in O(n) by scanning from the right.
Solution
import java.util.Arrays;
public class Main {
static int[] leaders(int[] a) {
int[] tmp = new int[a.length];
int count = 0, maxRight = Integer.MIN_VALUE;
for (int i = a.length - 1; i >= 0; i--) {
if (a[i] > maxRight) {
tmp[count++] = a[i];
maxRight = a[i];
}
}
int[] out = new int[count];
for (int i = 0; i < count; i++) out[i] = tmp[count - 1 - i]; // restore left-to-right order
return out;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(leaders(new int[]{16, 17, 4, 3, 5, 2})));
System.out.println(Arrays.toString(leaders(new int[]{1, 2, 3, 4})));
}
}
[17, 5, 2] [4]
Scanning from the right, an element is a leader exactly when it beats the maximum seen so far.
Discussion & Comments 0
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!