enjoyalgorithms

Find all Leaders in an Array

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.

Let's understand the problem

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.

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.

Discussed solution approaches

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

Brute force solution  using two nested loops 

Solution idea

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.

Solution code C++

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

Solution code Python

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

Solution analysis

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.

Efficient solution  using a single scan from right side

Solution idea

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

Solution code C++

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 code Python

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

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

Critical ideas to think!

  • 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?

Comparison of time and space complexities

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

Suggested coding problems to explore

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

More from EnjoyAlgorithms

Self-paced Courses and Blogs