Leaders in an Array

Problem Statement

Given an array arr of size n with all unique elements. Print all Leaders in the array in any order.

Example

Input: [2,4,6,3,1,2] Output: 6,3,2

Input: [1,3,6,9,2,5] Output: 9,5

Explanation

• In the first example, where Input: [2,4,6,3,1,2], Output: 6,3,2, we can see that the leaders are 6, 3, and 2 because

  • 2 is the rightmost element, so it is a leader.
  • 3 is greater than all the elements on its right side i.e. 3 is greater than 1 and 2, so it is a leader.
  • 6 is greater than all the elements on its right side i.e. 6 is greater than 3, 1, and 2, so it is a leader.

• In the second example where Input: [1,3,6,9,2,5], Output: 9,5, we can see that the leaders are 9 and 5 because

  • 5 is the rightmost element, so it is a leader.
  • 9 is greater than all the elements on its right side i.e. 9 is greater than 5, so it is a leader.

Constraints

$1 <= n <= 10^5$ $1 <= arr[i] <= 10^5$

Approach 1: Naive Approach (Using Two for Loops)

This is the Brute-Force method to find leaders in an array. In this approach, we will compare every element of the array to all the elements which are on its right side, if this element is greater than all the elements which are on its right side, then this element is one of the leaders in the array. We will use two nested loops, the outer loop will run n times and each time we will pick an element and see all the elements on its right side. If this element is greater than all the elements to its right side, then it is a leader and we will print it.

Algorithm

• Given an array arr of size n.
• Run a loop from i=0 to i=n-1
• Now create a new variable k and initialize it with the ith element i.e. k = arr[i]
• Now run the inner loop from j=i+1 to j=n-1
• If any element arr[j] is greater than or equal to k, then break out of the loop
• After the end of the inner loop, if j==n, then print k (because we did not find any element which is greater than or equal to k, which means this element is a leader).

C++ Implementation

Output

Java Implementation

Output

Python Implementation

Output

Approach 2: Scan from Right

In this approach, we will scan the array from right to left, and keep track of the maximum element (local maxima) till now which is greater than all the elements from the rightmost point (the rightmost point is the (n-1)th index) to the current point. If at any point we find that the current element is greater than the maximum element, we will print the current element because we know that it is greater than the maximum element till here, so it will definitely be greater than all the elements which are on its right side, so it is one of the leaders in the array and then we will update the maximum element.

Algorithm

• Given an array arr of size n.
• Create a variable named maximum and initialize it with 0.
• Run a loop from i=n-1 to i=0
• If at any point arr[i] is greater than maximum, then print arr[i], and update the maximum by doing maximum=arr[i]

C++ Implementation

Output

Java Implementation

Output

Python Implementation

Output

Complexity Analysis

Time Complexity Analysis

• In this approach, we are performing n operations by running a loop from i=n-1 to i=0, which will take O(N) time.

So the overall time complexity of this solution to find leaders in an array will be O(N)

Space Complexity Analysis

• In this approach, we are using only one variable i.e. maximum, which means that no auxiliary space is used here which will be considered as O(1) space.

So the overall space complexity of this solution to find leaders in an array will be O(1)

Time Complexity: O(N) Space Complexity: O(1)

Approach 3: Using the Stack Data Structure

In this approach, we will use the Stack data structure to store all leaders. In the previous approach, we saw that we got the output in the reverse order, because we were scanning from right to left, and each time we encountered a leader, we are printing it. But for getting the output in the correct order, we must reverse the output of the previous approach, which can be easily done with the help of a stack. We can find all the leaders of the array with the help of an approach similar to approach 2, and we can store them in the stack. Now after storing all the leaders in the stack, we can print the stack, so our output will be in the reverse order of the previous approach.