**Difficulty:** easy, **Asked-in:** Microsoft, Amazon, Adobe, Goldman Sachs

**Key takeaway:** An excellent problem to learn problem-solving using a single scan and updating output using variables.

Given an integer array X[] of size n, write a program to find all the leaders in the array X[]. An element is a leader if it is strictly greater than all the elements to its right side.

- The last element of an array is a leader by default.
- The largest element of an array is also a leader by default.
- Suppose all the array elements are unique.
- Ordering in the output doesn’t matter.

**Important note:** before moving on to the solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes.

Input: X[] = [16, 17, 4, 3, 5, 2], Output: [17, 5, 2]

Explanation: Element 2 is the rightmost element, so it is a leader by default. 17 and 5 are also leader elements because they are greater than all the elements on their right side.

Input: X[] = [6, 5, 4, 3, 2, 1], Output: [6, 5, 4, 3, 2, 1]

Explanation: All elements are leaders because they are greater than all the elements on their right side. Element 1 is the rightmost element, so it is a leader by default.

Input: X[] = [1, 2, 3, 4, 5, 6], Output: [6]

Explanation: Element 6 is the rightmost element, which is a leader by default. Otherwise, all elements are less than all on their right side.

- Brute force solution using two nested loops
- Efficient solution using a single scan from the right

Based on the definition, leaders are the elements in an array that are greater than all the elements on their right side. So, one basic idea would be to explore each element X[i] and check whether all the elements on the right side of the array are less than X[i] or not. If yes, we add it to the output. Otherwise, we ignore X[i] and move to the next element. To implement this, we can run two nested loops:

- The outer loop from
**i = 0 to n - 1**explores each element X[i] from left to right. - The inner loop from
**j = i + 1 to n - 1**compares X[i] with all the elements to its right side. If X[i] is greater than all the elements to its right side, X[i] is a leader element, and we add it to the output.

```
vector<int> findLeaders(int X[], int n)
{
vector<int> leaders;
for (int i = 0; i < n; i = i + 1)
{
int j = i + 1;
while (j < n)
{
if (X[i] < X[j])
break;
j = j + 1;
}
if (j == n)
leaders.push_back(X[i]);
}
return leaders;
}
```

```
def findLeaders(X, n):
leaders = []
for i in range(n):
j = i + 1
while j < n:
if X[i] < X[j]:
break
j = j + 1
if j == n:
leaders.append(X[i])
return leaders
```

We are running two nested loops and performing O(1) operations at each iteration. Therefore, the total number of loop iterations in the worst-case scenario is (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2. So, the time complexity in the worst-case scenario is O(1) * n(n - 1)/2 = **O(n^2)**.

Inside the inner loop, we move forward if (X[i] > X[j]), and we break the loop and move forward to the next iteration of the outer loop otherwise. So, the critical question is: what would be the scenarios for the worst and best-case inputs? Think about it!

The space complexity is **O(1)** because the leaders[] array is part of the output given in the problem. Therefore, we do not consider it as extra space.

Now, the critical question is: can we solve this problem in O(n) time complexity using a single traversal? Let's think about it!

An element X[i] is a leader if it is greater than the maximum among all the elements to its right side. Therefore, one idea would be to scan all the elements from right to left and keep track of the maximum so far using a variable **maxFromRight**. Whenever we find an **X[i] > maxFromRight**, it means that X[i] is a leader element that is greater than the maximum element on the right side. In other words, whenever **maxFromRight** changes its value, we have found a leader element. **Note:** The last element of the array is a leader by default, so we initialize **maxFromRight = X[n - 1]**.

```
vector<int> findLeaders(int X[], int n)
{
vector<int> leaders;
int maxFromRight = X[n - 1];
leaders.push_back(maxFromRight);
for (int i = n - 2; i >= 0; i = i - 1)
{
if (maxFromRight < X[i])
{
maxFromRight = X[i];
leaders.push_back(maxFromRight);
}
}
return leaders;
}
```

```
def findLeaders(X, n):
leaders = []
maxFromRight = X[n - 1]
leaders.append(maxFromRight)
for i in range(n - 2, -1, -1):
if maxFromRight < X[i]:
maxFromRight = X[i]
leaders.append(maxFromRight)
return leaders
```

We are running a single loop of size and performing an O(1) operation at each iteration. So time complexity = O(n) * O(1) = O(n). Space complexity = O(1).

- How can we modify the above solutions to store the output in a stable order or in the same order as they are present in the input?
- How can we modify the above code to handle the scenario of duplicate elements?
- Can we think of solving this problem using recursion? If yes, what would be the time and space complexity?
- Can we think of solving this problem using a stack? If yes, what would be the time and space complexity?

- Using two nested loops: Time = O(n^2), Space = O(1)
- Using a single scan: Time = O(n), Space = O(1)

- Number of buildings facing the sun
- Find next greater elements in an array
- Find equilibrium index of an array
- Move zeroes to the end of an array
- The minimum and maximum value in an array

Please write in the message below if you find anything incorrect, or you want to share more insight. Enjoy learning, Enjoy algorithms!

☆ 16-Week Live DSA Course

☆ 10-Week Live DSA Course

Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.

©2023 Code Algorithms Pvt. Ltd.

All rights reserved.