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.

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.

Discussed solution approaches

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

Solution approach 1: A brute force solution  using two nested loops 

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 approach 2: An efficient solution  using a single scan from the right

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!

Critical ideas to think!

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

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, or you know some different approaches to solve this problem. Enjoy learning, Enjoy algorithms!

More From EnjoyAlgorithms

Our weekly newsletter

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

Follow Us:

LinkedinMedium

© 2020 EnjoyAlgorithms Inc.

All rights reserved.