GATE CSE 2006 | Question: 17

Question

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 

• A. solves it in linear time using a left to right pass of the array
• B. solves it in linear time using a right to left pass of the array
• C. solves it using divide and conquer in time $\Theta (n\log n)$
• D. solves it in time $\Theta( n^2)$

Comments

Slight modification of Next greater element
 

int curr_max = arr[n-1];
cout << arr[n-1] << " is a leader" << endl; // last element is always a leader

for(int i = n - 2; i >= 0; i--){
    if(arr[i] > curr_max){
        cout << arr[i] << " is a leader" << endl;
        curr_max = arr[i];
    }
}

 

---

thank you very much

---

https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side

Answer 1

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; }

Comments

Ur coding will take O($n^{n}$) in worst case .... Bt the answer should be O($n$) ....

---

@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

---

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)