Leaders in an Array

64.1k
0

Problem Statement

Given an integer array nums, return all the leaders present in the array.

An element is a leader when no element strictly greater than it exists on its right side.

The rightmost element is always a leader because no element appears after it.

Return the leaders in the same left-to-right order in which they appear in nums.

Example 1

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

Output: [17, 5, 2]

Explanation: 17 stays greater than every value on the right side. 5 stays greater than 2. 2 is the rightmost value, so leader status is guaranteed.

Example 2

Input: nums = [10, 22, 12, 3, 0, 6]

Output: [22, 12, 6]

Explanation: 22 stays greater than every value after index 1. 12 stays greater than 3, 0, and 6. 6 is the rightmost value.

Example 3

Input: nums = [5, 4, 3, 2, 1]

Output: [5, 4, 3, 2, 1]

Explanation: Every value stays greater than all values on the right side, so every value becomes a leader.

Brute Force Approach

Whether an element is a leader depends entirely on the elements appearing after it.

The direct approach treats every element as a candidate and scans its complete right side. Finding even one greater value rejects the candidate. Otherwise, the element is added to the result.

Algorithm

  • Store the array size in n and create leaders to collect the elements that satisfy the leader condition in their original order.

  • Traverse every index and treat nums[index] as the current leader candidate.

  • Set isLeader to true before checking the elements on its right, since the candidate remains valid unless a strictly greater value is found.

  • Traverse from index + 1 to n - 1. If any value is greater than nums[index], set isLeader to false and stop checking because the current element can no longer be a leader.

  • If isLeader remains true, add nums[index] to leaders because no strictly greater element exists on its right.

  • Return leaders after every element has been checked.

Dry Run

Leaders in an Array Brute Force Dry Run.png

Leaders in an Array Brute Force Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> leadersInArray(vector<int>& nums) {
int n = nums.size();
vector<int> leaders;
// Check every element as a possible leader.
for (int index = 0; index < n; index++) {
bool isLeader = true;
/*
* A greater value on the right
* removes the current leader candidate.
*/
for (int right = index + 1; right < n; right++) {
if (nums[right] > nums[index]) {
isLeader = false;
break;
}
}
// Add the value only if no greater value was found.
if (isLeader) {
leaders.push_back(nums[index]);
}
}
return leaders;
}
};
int main() {
vector<int> nums = {10, 22, 12, 3, 0, 6};
Solution solution;
vector<int> leaders = solution.leadersInArray(nums);
for (int value : leaders) {
cout << value << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(N²), where N represents the array size. Every candidate may require comparison with every remaining element on its right.

Space Complexity: O(1) auxiliary space, because only loop variables and a Boolean flag are required. The returned list is excluded from auxiliary-space analysis.

Better Approach

Repeated right-side scans can be avoided by storing the maximum value available in every suffix.

Once the suffix maximums are prepared, each candidate only needs to be compared with the maximum value strictly on its right.

Algorithm

  • Store the array size in n. If the array is empty, return an empty list because no leaders exist.

  • Create suffixMax, where suffixMax[index] stores the greatest value from index through n - 1. This allows the complete right side of any element to be represented by a single value.

  • Set suffixMax[n - 1] to the rightmost element, then build the remaining values from right to left using the maximum of nums[index] and suffixMax[index + 1].

  • Traverse nums from left to right so that leaders are collected directly in their original order.

  • For every index before the last, add nums[index] when it is greater than or equal to suffixMax[index + 1], because no strictly greater value then exists on its right. Add the rightmost element as well because it always qualifies.

  • Return the completed leaders list.

Dry Run

Leaders in an Array Better Appraoch Dry Run.png

Leaders in an Array Better Appraoch Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> leadersInArray(vector<int>& nums) {
int n = nums.size();
// No leaders exist in an empty array.
if (n == 0) {
return {};
}
vector<int> suffixMax(n);
suffixMax[n - 1] = nums[n - 1];
/*
* Store the greatest value available
* from each index to the end.
*/
for (int index = n - 2; index >= 0; index--) {
suffixMax[index] =
max(nums[index], suffixMax[index + 1]);
}
vector<int> leaders;
for (int index = 0; index < n - 1; index++) {
/*
* Equality is allowed because only a
* strictly greater value removes leader status.
*/
if (nums[index] >= suffixMax[index + 1]) {
leaders.push_back(nums[index]);
}
}
// The rightmost element is always a leader.
leaders.push_back(nums[n - 1]);
return leaders;
}
};
int main() {
vector<int> nums = {10, 22, 12, 3, 0, 6};
Solution solution;
vector<int> leaders = solution.leadersInArray(nums);
for (int value : leaders) {
cout << value << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N represents the array size. One traversal builds the suffix maximum array, and another traversal collects the leaders.

Space Complexity: O(N), because suffixMax stores one value for every array position. The returned list is excluded from auxiliary-space analysis.

Optimal Approach

While traversing from right to left, every already-processed element lies on the right side of the current candidate.

A single variable, maxRight, can therefore summarize the greatest value seen on the right. The current value becomes a leader when it is greater than or equal to maxRight.

Because leaders are discovered from right to left, the collected result must be reversed before returning.

Algorithm

  • Store the array size in n. If the array is empty, return an empty list.

  • Initialize maxRight with the rightmost element and add that element to leaders, since no value exists to its right.

  • Traverse from index n - 2 toward 0. At each step, maxRight represents the greatest value among all elements already processed on the right.

  • If nums[index] >= maxRight, add the current value to leaders, because no strictly greater element exists on its right.

  • Update maxRight with the larger of maxRight and nums[index] so it remains the maximum value available to the next candidate on the left.

  • Reverse leaders before returning, since the right-to-left traversal discovers leaders in reverse order.

Dry Run

Leaders in an Array Optimal Dry Run.png

Leaders in an Array Optimal Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> leadersInArray(vector<int>& nums) {
int n = nums.size();
// No leaders exist in an empty array.
if (n == 0) {
return {};
}
vector<int> leaders;
int maxRight = nums[n - 1];
// The rightmost element is always a leader.
leaders.push_back(nums[n - 1]);
for (int index = n - 2; index >= 0; index--) {
/*
* Equality is valid because only a
* strictly greater right value disqualifies it.
*/
if (nums[index] >= maxRight) {
leaders.push_back(nums[index]);
}
// Keep the greatest value seen on the right.
maxRight = max(maxRight, nums[index]);
}
/*
* Leaders were collected from right to left,
* so reverse them to restore original order.
*/
reverse(leaders.begin(), leaders.end());
return leaders;
}
};
int main() {
vector<int> nums = {10, 22, 12, 3, 0, 6};
Solution solution;
vector<int> leaders = solution.leadersInArray(nums);
for (int value : leaders) {
cout << value << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N represents the array size. One right-to-left traversal identifies the leaders, and reversing the collected list requires at most O(N) time.

Space Complexity: O(1) auxiliary space, because only maxRight and loop variables require extra storage. The returned list is excluded from auxiliary-space analysis.

Interview follow-up Questions

Yes. Under the “no greater value on the right” definition, equality remains valid. For nums = [7, 7, 5], both occurrences of 7 qualify.

Arrays

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0...

67.1k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

98.4k
Comments0