LearnFrenzy
Sign in Take a free test

Arrays in Java · Java Array Programs · Question 7

Find leaders in an array in Java Solution, output & explanation

  • Program
  • Medium
  • 0 comments
  • Answer explained
  • Moderated community
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
Main.java
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})));
    }
}

Output Verified by compiling and running

[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!

Post your comment

Comments appear after a quick review by our team.

Search LearnFrenzy

Esc

Quick links