58 votes 58 votes An element in an array $X$ is called a leader if it is greater than all elements to the right of it in $X$. The best algorithm to find all leaders in an array solves it in linear time using a left to right pass of the array solves it in linear time using a right to left pass of the array solves it using divide and conquer in time $\Theta (n\log n)$ solves it in time $\Theta( n^2)$ Algorithms gatecse-2006 algorithms normal algorithm-design + – Rucha Shelke asked Sep 17, 2014 edited Jun 23, 2018 by Shikha Mallick Rucha Shelke 17.7k views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments AMAN_SINHA commented Apr 9, 2020 reply Follow Share This Program will also work to find all such LEADER. #include<stdio.h> #include<conio.h> void main() {int i; int a[]={10,2,5,7,3,1,4,3}; int temp=0; for(i=sizeof(a)/sizeof(int)-1;i>=0;i--) {if(a[i]>temp) { printf("%d ",a[i]); temp=a[i]; } } getch(); } 0 votes 0 votes Kiyoshi commented May 26, 2021 reply Follow Share By right to left pass of the array we can do in O(n) time. #include <iostream> #include<stdio.h> using namespace std; int main() { int n; scanf("%d",&n); int a[n],max; for(int i=0;i<n;i++){ scanf("%d ",&a[i]); } max=a[n-1]; printf("leaders are = %d ",max); for(int i=n-2;i>=0;i--){ if(a[i]>max){ max=a[i]; printf("%d ",max); } } return 0; } https://ideone.com/ejaIFg By left to right pass of the array we can do in O(n^2) time. #include <iostream> #include<stdio.h> using namespace std; int main() { int n; scanf("%d",&n); int a[n],max,count; for(int i=0;i<n;i++){ scanf("%d ",&a[i]); } printf("leaders are ="); for(int i=0;i<n;i++){ count=1; for(int j=i+1;j<n;j++){ if(a[i]<a[j]){ count=0; } } if(count==1){ printf("%d ",a[i]); } } return 0; } https://ideone.com/fupNEv 1 votes 1 votes palashbehra5 commented Nov 18, 2021 reply Follow Share They pretty much handed out a huge hint in the options. 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes I think, that this problem is only reverse sorting or putting elements in descending order, In order to do that start scanning from right. So. ANSWER is B. Jhaiyam answered Jul 5, 2020 Jhaiyam comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes I have fully explained this question and gave the answer in short period of time just go through the link. I hope it’ll help you https://youtu.be/hu9RWj1YxEY Junaid khan290 answered Sep 13, 2020 Junaid khan290 comment Share Follow See all 0 reply Please log in or register to add a comment.
–1 votes –1 votes Use two loops. The outer loop runs from 0 to size – 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. #include<iostream> using namespace std; /*C++ Function to print leaders in an array */ void printLeaders(int arr[], int size) { for (int i = 0; i < size; i++) { int j; for (j = i+1; j < size; j++) { if (arr[i] <= arr[j]) break; } if (j == size) // the loop didn't break cout << arr[i] << " "; } } /* Driver program to test above function */ int main() { int arr[] = {16, 17, 4, 3, 5, 2}; int n = sizeof(arr)/sizeof(arr[0]); printLeaders(arr, n); return 0; } Paras Nath answered Nov 11, 2017 Paras Nath comment Share Follow See all 3 Comments See all 3 3 Comments reply Puja Mishra commented Jan 6, 2018 reply Follow Share Ur coding will take O($n^{n}$) in worst case .... Bt the answer should be O($n$) .... 0 votes 0 votes Vinnakota vineela commented Sep 16, 2018 reply Follow Share @puja for option a y it can't be n*n for n elements we are traversing n times approximately so n*n how will u conclude it will be n^n plzzzzzz tell me if I'm wrong let me know how to think 0 votes 0 votes Ram Swaroop commented Feb 10, 2020 reply Follow Share Why n*n we traversing from right to left one time so it should be o(n). If they ask worst case then o(n^2) 0 votes 0 votes Please log in or register to add a comment.