**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.

**Problem note**

- 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. Enjoy problem-solving!

**Example 1**

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.

**Example 2**

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.

**Example 3**

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.

- A brute force solution using two nested loops
- An efficient solution using a single scan from the right

**Solution idea**

Based on the definition: leaders are the elements in an array greater than all the elements on the right side. So one basic idea would be to explore each element X[i] and check whether all elements on the right side of the array are less than X[i] or not. If yes, then 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 the left to right. - The inner loop from
**j = i + 1 to n - 1**compare 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.

**Solution pseudocode**

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

**Solution analysis**

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

Inside the inner loop, we are moving forward if (X[i] > X[j]). Otherwise, we break the loop and move forward to the next iteration of the outer loop. So the critical question is: what would be the scenario of worst and best case input? Think!

Space complexity = **O(1)** because leaders[] array is the part of the output given in the problem. So we will not consider it as an extra space.

**Solution idea**

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

An element X[i] is a leader if X[i] is greater than the maximum among all the elements to its right side. So one idea would be to scan all the elements from right to left and keep track of the max so far using a variable **maxFromRight.** Whenever we find an **X[i] > maxFromRight**, it means X[i] is a leader element that is greater than the max 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].

**Solution pseudocode**

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

**Solution analysis**

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)**. Think!

**Important note:** we recommend transforming the above pseudo-codes into a favorite programming language (C, C++, Java, Python, etc.) and verifying all the test cases. Enjoy programming!

- How can we modify the above solutions to store the output in a stable order or 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, then what would be the time and space complexity?
- Can we think of solving this problem using a stack? If yes, then 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, or you know some different approaches to solve this problem. Enjoy learning, Enjoy algorithms!

Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.