Problem:
We need to print all the leaders present in the array. Element is the leader if it is greater than right side of elements.
For example:
|
1 2 3 4 |
arr[]={14, 12, 70, 15, 99, 65, 21, 90} Here 99 and 90 are leader elements |
Solution:
Solution 1:
Use two loops. Outer loop to iterate over array elements and inner loop to check for right elements of the array. If current element is greater than right elements than it is a leader.
Java code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public static void findLeadersInAnArrayBruteForce(int arr[]) { System.out.println("Finding leaders in an array using brute force : "); for (int i = 0; i < arr.length; i++) { boolean isLeader=true; for (int j = i+1; j < arr.length; j++) { if(arr[i] <= arr[j]) { isLeader=false; break; } } if(isLeader) System.out.print(arr[i]+" "); } } |
Time complexity : o(N^2)
Solution 2:
Lets find more optimized solution
We will use property that rightmost element is always a leader.
- We will start from rightmost element and track max.
- Whenever we get new max, that element is a leader.
Java code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public static void findLeadersInAnArray(int arr[]) { System.out.println("Finding leaders in an array : "); int rightMax=arr[arr.length-1]; // Rightmost will always be a leader System.out.print(rightMax+" "); for (int i = arr.length-2; i>=0; i--) { if(arr[i] > rightMax) { rightMax=arr[i]; System.out.print(" "+rightMax); } } } |
Time complexity : o(N)
Java Program to find leaders in the array:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
package org.arpit.java2blog; public class FindLeadersInArrayMain { public static void main(String[] args) { int arr[]={14, 12, 70, 15, 99, 65, 21, 90}; findLeadersInAnArrayBruteForce(arr); System.out.println("n=================="); findLeadersInAnArray(arr); } public static void findLeadersInAnArrayBruteForce(int arr[]) { System.out.println("Finding leaders in an array using brute force : "); for (int i = 0; i < arr.length; i++) { boolean isLeader=true; for (int j = i+1; j < arr.length; j++) { if(arr[i] <= arr[j]) { isLeader=false; break; } } if(isLeader) System.out.print(arr[i]+" "); } } public static void findLeadersInAnArray(int arr[]) { System.out.println("Finding leaders in an array : "); int rightMax=arr[arr.length-1]; // Rightmost will always be a leader System.out.print(rightMax+" "); for (int i = arr.length-2; i>=0; i--) { if(arr[i] > rightMax) { rightMax=arr[i]; System.out.print(" "+rightMax); } } } } |
|
1 2 3 4 5 6 7 |
Finding leaders in an array using brute force 99 90 ================== Finding leaders in an array : 90 99 |
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
