Leaders in an array

Given an array of integers, print the leaders in the array. A leader is an element which is larger than all the elements in the array to its right.
For example:
Input Array:
{ 98, 23, 54, 12, 20, 7, 27 }
Output:
Leaders- 27 54 98


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Algorithm/Insights

Start from the right keeping track of largest element (currentLeader). If a larger element is found, then print it and set currentLeader to the current element.
Note that the last element is a leader since there is no element to its right.
The solution can be visualized by considering array elements as towers and printing towers which are visible if seen through right view of the array.
Please note that leaders will be seen in sorted order when seen from right(right view of the towers).


Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.saurabh;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Given an array of integers, print the leaders in the array.
 * A leader is an element which is larger than all the elements
 * in the array to its right. 
 *
 * @author Saurabh
 */
public class LeaderElements {

    public static void printLeaders(int[] input) {
        if(input == null || input.length == 0) {
            return;
        }
        int inputSize = input.length;
        int currentLeader = input[inputSize - 1];
        System.out.print("Leaders- ");
        System.out.print(currentLeader + " ");
        for (int i = inputSize - 2; i >= 0; i--) {
            if(input[i] > currentLeader) {
                currentLeader = input[i];
                System.out.print(currentLeader + " ");
            }
        }
    }
    public static void main(String[] args) {
        int[] input = { 98, 23, 54, 12, 20, 7, 27 };
        printLeaders(input);
    }
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.


    Saurabh Kumar