edited by
17,694 views
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 

  1. solves it in linear time using a left to right pass of the array
  2. solves it in linear time using a right to left pass of the array
  3. solves it using divide and conquer in time $\Theta (n\log n)$
  4. solves it in time $\Theta( n^2)$
edited by

7 Answers

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.

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

}

Answer:

Related questions