Leaders in an Array
![DSA Problem Solving for Interviews using Java](https://www.scaler.com/topics/images/jitender_punia.webp)
Problem Statement
Given an array arr of size n with all unique elements. Print all Leaders in the array in any order.
Note: A leader is an element of the array if it is greater than all the elements to its right side in the array. The rightmost element is always a leader in an array.
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
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
Complexity Analysis
Time Complexity Analysis
- In this approach, we perform n operations by running a loop from i=1 to i=n, which will take O(N) time.
- Inside the loop, we are performing n-i-1 operations by running the loop from j=i+1 to j=n-1, which can take O(N) time complexity in the worst case (when i is equal to 0)
So the overall time complexity of this solution to find leaders in an array will be
Space Complexity Analysis
- In this approach, we are using only one variable i.e. k, 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*N) Space Complexity: O(1)
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.
Note: A Stack is a linear data structure that follows the principle of Last in First out (LIFO). It means if we push that the last element inserted into the stack will be the first one to be removed.
Algorithm
- Given an array arr of size n.
- Create a stack name s and push arr[n-1] into the stack.
- Run a loop from i=n-2 to i=0
- If arr[i] is greater than the topmost element of the stack, push arr[i] into the stack
- After the loop is over print all the elements which are present in the stack, because these elements are the leaders of this array as they are greater than all the elements which are on their right side.
C++ Implementation
Output
Java Implementation
Output
Python Implementation
Output
Complexity Analysis
Time Complexity Analysis
- In the first step, we perform n operations by running a loop from i=n-2 to i=0, which will take O(N) time.
- In the second step, we may perform at most n operations, because we are traversing the stack, which can contain n elements in the worst case.
So the overall time complexity of this solution to find leaders in an array will be .
Space Complexity Analysis
In this approach, we are using a stack, which will take O(N) space in worst-case
So the overall space complexity of this solution to find leaders in an array will be O(N)
Time Complexity: O(N) Space Complexity: O(N)
Conclusion
In this quick tutorial, we have discussed 3 different approaches for finding leaders in an array.
- In Approach 1, we used two for loops, which is the naive method, and took O(N*N) time complexity.
- In Approach 2, we scanned the array from right to left, and updated the maximum, this is the best approach to solve this problem which took just O(N) time complexity and O(1) space complexity
- In Approach 3, we used stack data structure, which was the extension of approach 2, to keep the track of maximum elements on top of the stack.