Problem: You are given an array. You have to write a program that will print all the leaders in the array. An element is leader if it is greater than all the elements to its right side. And the rightmost element is always a leader.
For example array {6, 7, 4, 3, 5, 2}, leaders are 7, 5 and 2.
This is very common data structure interview question.
Solution:
Method 1 (Brute Force)
Use two loops. The outer loop runs from 0 to length – 1 and one by one picks all elements from left to right. The inner loop compares the picked element to all the elements to its right side. If the picked element is greater than all the elements to its right side, then the picked element is the leader.
Time Complexity: O(n*n)
Method 2 (Scan the array from right)
Start Traversing from the right side of the array, and keep the highest element in a variable,if we find any element greater then this variable print it and update the variable with the new value.
void printLeaders(int arr[], int n) { int maximum = arr[n-1]; int i; // Rightmost element is always leader printf("%d ", maximum); for(i = n-2; i >= 0; i--) { if(maximum < arr[i]) { printf("%d ", arr[i]); maximum = arr[i]; } } } int main() { int arr[] = {6, 7, 4, 3, 5, 2}; printLeaders(arr, 6); return 0; }
Output: 2 5 7
Time Complexity: O(n)