Leaders in an Array

Intuition

The most naive thing that comes to mind is if at all any element on right is greater than the current element, then the current element can never be a leader.

Approach

Iterate through each element of the array with the variable let's say i and take a boolean variable leader set at true initially which will tell if nums[i] is a leader or not.

For each i, iterate through the elements to the right (from i+1 to the end of the array) with the variable j & check if nums[j] is greater than nums[i], if so, reinitialize the variable leader as false and break.

After exiting from the inner loop, check if leader equals true, if so add nums[i] to ans vector. Finally return the answer vector.

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    //Function to find leaders in an array.
    vector<int> leaders(vector<int>& nums) {
        vector<int> ans;

        // Iterate through each element in nums
        for (int i = 0; i < nums.size(); i++) {
            bool leader = true;

            /* Check whether nums[i] is greater
            than all elements to its right*/
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[j] >= nums[i]) {
                    /* If any element to the right is greater 
                    or equal, nums[i] is not a leader*/
                    leader = false;
                    break;
                }
            }

            // If nums[i] is a leader, add it to the ans vector
            if (leader) {
                ans.push_back(nums[i]);
            }
        }

       //Return the leaders 
        return ans;
    }
};

int main() {
    vector<int> nums = {1, 2, 5, 3, 1, 2};

    // Create an instance of the Solution class
    Solution finder;

    // Get leaders using class method
    vector<int> ans = finder.leaders(nums);

    cout << "Leaders in the array are: ";
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    cout << endl;

    return 0;
}
import java.util.*;

class Solution {
    //Function to find leaders in an array.
    public ArrayList<Integer> leaders(int[] nums) {
        ArrayList<Integer> ans = new ArrayList<>();

        // Iterate through each element in nums
        for (int i = 0; i < nums.length; i++) {
            boolean leader = true;

            /* Check whether nums[i] is greater
            than all elements to its right */
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] >= nums[i]) {
                    /* If any element to the right is greater 
                    or equal, nums[i] is not a leader */
                    leader = false;
                    break;
                }
            }

            // If nums[i] is a leader, add it to the ans list
            if (leader) {
                ans.add(nums[i]);
            }
        }

        // Return the leaders 
        return ans;
    }
}

class Main {
    public static void main(String[] args) {
        int[] nums = {1, 2, 5, 3, 1, 2};

        // Create an instance of the Solution class
        Solution finder = new Solution();

        // Get leaders using class method
        ArrayList<Integer> ans = finder.leaders(nums);

        System.out.print("Leaders in the array are: ");
        for (int leader : ans) {
            System.out.print(leader + " ");
        }
        System.out.println();
    }
}
class Solution:
    # Function to find leaders in an array.
    def leaders(self, nums):
        ans = []

        # Iterate through each element in nums
        for i in range(len(nums)):
            leader = True

            '''Check whether nums[i] is greater
            than all elements to its right'''
            for j in range(i + 1, len(nums)):
                if nums[j] >= nums[i]:
                    '''If any element to the right is greater 
                    or equal, nums[i] is not a leader'''
                    leader = False
                    break

            # If nums[i] is a leader, add it to the ans list
            if leader:
                ans.append(nums[i])

        # Return the leaders
        return ans


# Main method
nums = [1, 2, 5, 3, 1, 2]

# Create an instance of the Solution class
finder = Solution()

# Get leaders using class method
ans = finder.leaders(nums)

print("Leaders in the array are: ", end="")
for leader in ans:
    print(leader, end=" ")
print()
class Solution {
    // Function to find leaders in an array.
    leaders(nums) {
        let ans = [];

        // Iterate through each element in nums
        for (let i = 0; i < nums.length; i++) {
            let leader = true;

            /* Check whether nums[i] is greater
            than all elements to its right */
            for (let j = i + 1; j < nums.length; j++) {
                if (nums[j] >= nums[i]) {
                    /* If any element to the right is greater 
                    or equal, nums[i] is not a leader */
                    leader = false;
                    break;
                }
            }

            // If nums[i] is a leader, add it to the ans array
            if (leader) {
                ans.push(nums[i]);
            }
        }

        // Return the leaders
        return ans;
    }
}

// Main method
let nums = [1, 2, 5, 3, 1, 2];

// Create an instance of the Solution class
let finder = new Solution();

// Get leaders using class method
let ans = finder.leaders(nums);

console.log("Leaders in the array are: " + ans.join(" "));

Complexity Analysis

Time Complexity: O(N²), where N is the length of that array, as 2 nested for loops are used to traverse the array. Space Complexity: O(1), as extra space to store answer is not considered.

Intuition

Think of a parade where each person in a line holds a flag with a number on it, representing their importance. You start observing the parade from the last person, moving towards the front. Initially, the last person is the most important (since there's no one else behind them).

As you move forward, compare each person's flag number to the highest flag number seen so far. If someone's flag number is higher than the highest that is seen, they stand out as a leader because they have a higher number than anyone behind them.

Approach

Set a variable max to the last element of the array (nums[sizeOfArray - 1]), as the last element is always a leader.

Create an empty list ans to store the leader elements and add the last element of the array to this list initially, as it is always a leader.

Start from the second last element (index = sizeOfArray - 2) and move towards the first element (index = 0)

For each element, compare it with the max variable. If the current element is greater than max, add this element to the ans list and update max to the current element.

The ans list now contains all the leader elements in the reverse order of them appearing in the array. Reverse the ans list and return.

Dry Run

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    //Function to find the leaders in an array.
    vector<int> leaders(vector<int>& nums) {
        vector<int> ans;
        
        if(nums.empty()) {
            return ans;
        }
        
        // Last element of the vector is always a leader
        int max = nums[nums.size() - 1];
        ans.push_back(nums[nums.size() - 1]);
        
        // Check elements from right to left
        for (int i = nums.size() - 2; i >= 0; i--) {
            if (nums[i] > max) {
                ans.push_back(nums[i]);
                max = nums[i];
            }
        }
        
        /* Reverse the vector to match
        the required output order*/
        reverse(ans.begin(), ans.end());
        
        //Return the leaders
        return ans;
    }
};

int main() {
    vector<int> nums = {10, 22, 12, 3, 0, 6};
    
    // Create an instance of the Solution class
    Solution finder;
    
    // Get leaders using class method
    vector<int> ans = finder.leaders(nums);
    
    cout << "Leaders in the array are: ";
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    cout << endl;
    
    return 0;
}
import java.util.*;

class Solution {
    // Function to find the leaders in an array.
    public ArrayList<Integer> leaders(int[] nums) {
        ArrayList<Integer> ans = new ArrayList<>();
        
        if (nums.length == 0) {
            return ans;
        }
        
        // Last element of the array is always a leader
        int max = nums[nums.length - 1];
        ans.add(nums[nums.length - 1]);
        
        // Check elements from right to left
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] > max) {
                ans.add(nums[i]);
                max = nums[i];
            }
        }
        
        /* Reverse the list to match
        the required output order */
        Collections.reverse(ans);
        
        // Return the leaders
        return ans;
    }
}

class Main {
    public static void main(String[] args) {
        int[] nums = {10, 22, 12, 3, 0, 6};
        
        // Create an instance of the Solution class
        Solution finder = new Solution();
        
        // Get leaders using class method
        ArrayList<Integer> ans = finder.leaders(nums);
        
        System.out.print("Leaders in the array are: ");
        for (int leader : ans) {
            System.out.print(leader + " ");
        }
        System.out.println();
    }
}
class Solution:
    # Function to find the leaders in an array.
    def leaders(self, nums):
        ans = []
        
        if not nums:
            return ans
        
        # Last element of the list is always a leader
        max_val = nums[-1]
        ans.append(nums[-1])
        
        # Check elements from right to left
        for i in range(len(nums) - 2, -1, -1):
            if nums[i] > max_val:
                ans.append(nums[i])
                max_val = nums[i]
        
        '''Reverse the list to match
        the required output order'''
        ans.reverse()
        
        # Return the leaders
        return ans

# Main method
nums = [10, 22, 12, 3, 0, 6]

# Create an instance of the Solution class
finder = Solution()

# Get leaders using class method
ans = finder.leaders(nums)

print("Leaders in the array are: ", end="")
for leader in ans:
    print(leader, end=" ")
print()
class Solution {
    // Function to find the leaders in an array.
    leaders(nums) {
        let ans = [];
        
        if (nums.length === 0) {
            return ans;
        }
        
        // Last element of the array is always a leader
        let max = nums[nums.length - 1];
        ans.push(nums[nums.length - 1]);
        
        // Check elements from right to left
        for (let i = nums.length - 2; i >= 0; i--) {
            if (nums[i] > max) {
                ans.push(nums[i]);
                max = nums[i];
            }
        }
        
        /* Reverse the array to match
        the required output order */
        ans.reverse();
        
        // Return the leaders
        return ans;
    }
}

// Main method
let nums = [10, 22, 12, 3, 0, 6];

// Create an instance of the Solution class
let finder = new Solution();

// Get leaders using class method
let ans = finder.leaders(nums);

console.log("Leaders in the array are: " + ans.join(" "));

Complexity Analysis

Time Complexity:O(N), for single traversal of array , where N is the length of that array. Space Complexity: O(1), as extra space to store answer is not considered.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Complexity Analysis

Intuition

Approach

Dry Run

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts