Write a javascript function that find leaders from an input array.
In an array, an element is considered a "leader" if it is greater than all the elements to its right. To find all the leader elements in an array, you can use various approaches. I'll outline a few methods and provide a code example for each.
Input: array = [16, 17, 4, 3, 5, 2]
Output: [17, 5, 2]
Input: array = [7, 10, 4, 3, 6, 5]
Output: [10, 6, 5]
Input: array = [2]
Output: [2]
Input: array = []
Output: Throw error => Input must be a non-empty array
function findLeaders(arr) {
if (!Array.isArray(arr) || arr.length === 0) {
throw new Error('Input must be a non-empty array');
}
const leaders = [];
let maxFromRight = arr[arr.length - 1];
leaders.push(maxFromRight);
for (let i = arr.length - 2; i >= 0; i--) {
if (arr[i] > maxFromRight) {
maxFromRight = arr[i];
leaders.push(maxFromRight);
}
}
return leaders.reverse();
}
const array1 = [16, 17, 4, 3, 5, 2];
findLeaders(array1); //output: [17, 5, 2]
const array2 = [7, 10, 4, 3, 6, 5];
findLeaders(array2); //output: [10, 6, 5]
const array3 = [2];
findLeaders(array3); //output: [2]
const array4 = [];
findLeaders(array4); //Throw error => Input must be a non-empty array
Right to Left Traversal: Begin from the end of the array and track the maximum element seen so far.
Add Leaders: If the current element is greater than the tracked maximum, update the maximum and add to the list of leaders.
Efficient with O(n) time complexity.
Requires only constant space O(1) excluding the output.
Requires reversing the result at the end.
function findLeadersBruteForce(arr) {
if (!Array.isArray(arr) || arr.length === 0) {
throw new Error('Input must be a non-empty array');
}
const leaders = [];
const n = arr.length;
for (let i = 0; i < n; i++) {
let isLeader = true;
for (let j = i + 1; j < n; j++) {
if (arr[i] <= arr[j]) {
isLeader = false;
break;
}
}
if (isLeader) {
leaders.push(arr[i]);
}
}
return leaders;
}
const array1 = [16, 17, 4, 3, 5, 2];
findLeadersBruteForce(array1); //output: [17, 5, 2]
const array2 = [7, 10, 4, 3, 6, 5];
findLeadersBruteForce(array2); //output: [10, 6, 5]
const array3 = [2];
findLeadersBruteForce(array3); //output: [2]
const array4 = [];
findLeadersBruteForce(array4); //Throw error => Input must be a non-empty array
Nested Loop: For each element, verify if it is greater than all elements to its right.
Leader Check: If an element is greater than all elements to its right, it is a leader.
Simple to understand and implement.
Time complexity of O(n^2), which can be inefficient for large arrays.
function findLeadersUsingStack(arr) {
if (!Array.isArray(arr) || arr.length === 0) {
throw new Error('Input must be a non-empty array');
}
const leaders = [];
const stack = [];
const n = arr.length;
// Traverse the array from right to left
for (let i = n - 1; i >= 0; i--) {
// If the stack is empty or the current element is greater than the top of the stack
if (stack.length === 0 || arr[i] > stack[stack.length - 1]) {
stack.push(arr[i]);
}
}
// The stack will have the leaders in reverse order, so reverse it
return stack.reverse();
}
const array1 = [16, 17, 4, 3, 5, 2];
findLeadersUsingStack(array1); //output: [17, 5, 2]
const array2 = [7, 10, 4, 3, 6, 5];
findLeadersUsingStack(array2); //output: [10, 6, 5]
const array3 = [2];
findLeadersUsingStack(array3); //output: [2]
const array4 = [];
findLeadersUsingStack(array4); //Throw error => Input must be a non-empty array
Stack Usage: Traverse the array from right to left and use the stack to keep track of leaders.
Reverse Stack: The stack contains leaders in reverse order, so reverse it at the end.
Efficient with O(n) time complexity.
Stack simplifies the process of finding leaders.
Uses additional space for the stack.
function findLeadersDivideAndConquer(arr) {
if (!Array.isArray(arr) || arr.length === 0) {
throw new Error('Input must be a non-empty array');
}
function findLeadersInRange(start, end) {
if (start === end) return [arr[start]];
const mid = Math.floor((start + end) / 2);
const leftLeaders = findLeadersInRange(start, mid);
const rightLeaders = findLeadersInRange(mid + 1, end);
let rightMax = Math.max(...rightLeaders);
return leftLeaders.filter(x => x > rightMax).concat(rightLeaders);
}
return findLeadersInRange(0, arr.length - 1);
}
const array1 = [16, 17, 4, 3, 5, 2];
findLeadersDivideAndConquer(array1); //output: [17, 5, 2]
const array2 = [7, 10, 4, 3, 6, 5];
findLeadersDivideAndConquer(array2); //output: [10, 6, 5]
const array3 = [2];
findLeadersDivideAndConquer(array3); //output: [2]
const array4 = [];
findLeadersDivideAndConquer(array4); //Throw error => Input must be a non-empty array
Divide and Conquer: Split the array into two halves, recursively find leaders in each half, and merge the results.
Combine Results: Compare leaders from both halves to determine the final list of leaders.
Can be elegant and fit well with divide-and-conquer strategies.
More complex and less intuitive than simple iteration-based solutions.
function findLeadersUsingFunctional(arr) {
if (!Array.isArray(arr) || arr.length === 0) {
throw new Error('Input must be a non-empty array');
}
const maxFromRight = [];
let currentMax = -Infinity;
for (let i = arr.length - 1; i >= 0; i--) {
if (arr[i] > currentMax) {
currentMax = arr[i];
maxFromRight[i] = arr[i];
} else {
maxFromRight[i] = currentMax;
}
}
return arr.filter((value, index) => value === maxFromRight[index]);
}
const array1 = [16, 17, 4, 3, 5, 2];
findLeadersUsingFunctional(array1); //output: [17, 5, 2]
const array2 = [7, 10, 4, 3, 6, 5];
findLeadersUsingFunctional(array2); //output: [10, 6, 5]
const array3 = [2];
findLeadersUsingFunctional(array3); //output: [2]
const array4 = [];
findLeadersUsingFunctional(array4); //Throw error => Input must be a non-empty array
Mapping Maximums: Compute the maximum values from the right and use filter to find leaders.
Functional Approach: Uses functional programming constructs for a more declarative style.
Concise and expressive code.
Leverages functional programming paradigms.
May be less intuitive for those unfamiliar with functional programming.
function findLeadersUsingHelperArray(arr) {
if (!Array.isArray(arr) || arr.length === 0) {
throw new Error('Input must be a non-empty array');
}
const n = arr.length;
const maxFromRight = new Array(n);
maxFromRight[n - 1] = arr[n - 1];
// Fill the maxFromRight array
for (let i = n - 2; i >= 0; i--) {
maxFromRight[i] = Math.max(arr[i], maxFromRight[i + 1]);
}
// Find leaders
const leaders = [];
for (let i = 0; i < n; i++) {
if (arr[i] > maxFromRight[i + 1] || i === n - 1) {
leaders.push(arr[i]);
}
}
return leaders;
}
const array1 = [16, 17, 4, 3, 5, 2];
findLeadersUsingHelperArray(array1); //output: [17, 5, 2]
const array2 = [7, 10, 4, 3, 6, 5];
findLeadersUsingHelperArray(array2); //output: [10, 6, 5]
const array3 = [2];
findLeadersUsingHelperArray(array3); //output: [2]
const array4 = [];
findLeadersUsingHelperArray(array4); //Throw error => Input must be a non-empty array
Helper Array: Store the maximum values to the right of each element and then determine the leaders.
Efficiency: Good balance of space and time complexity.
Efficient and straightforward with O(n) time complexity.
Requires extra space for the helper array.
function findLeadersUsingObject(arr) {
if (!Array.isArray(arr) || arr.length === 0) {
throw new Error('Input must be a non-empty array');
}
const leaders = [];
let maxFromRight = -Infinity;
for (let i = arr.length - 1; i >= 0; i--) {
if (arr[i] > maxFromRight) {
leaders.push(arr[i]);
maxFromRight = arr[i];
}
}
return leaders.reverse();
}
const array1 = [16, 17, 4, 3, 5, 2];
findLeadersUsingObject(array1); //output: [17, 5, 2]
const array2 = [7, 10, 4, 3, 6, 5];
findLeadersUsingObject(array2); //output: [10, 6, 5]
const array3 = [2];
findLeadersUsingObject(array3); //output: [2]
const array4 = [];
findLeadersUsingObject(array4); //Throw error => Input must be a non-empty array
Tracking Maximums: Use a simple variable to track the maximum value and push leaders to an array.
Reverse Result: The results are in reverse order and need to be reversed.
Simple and efficient with O(n) time complexity.
Uses minimal space.
Requires reversing the result array.
function findLeadersUsingFunctionalReduce(arr) {
if (!Array.isArray(arr) || arr.length === 0) {
throw new Error('Input must be a non-empty array');
}
// Compute maximum values from the right
const maxFromRight = arr.reduceRight((acc, current, index) => {
if (current > acc.max) {
acc.max = current;
acc.leaders.push(current);
}
return acc;
}, { max: -Infinity, leaders: [] });
return maxFromRight.leaders.reverse();
}
const array1 = [16, 17, 4, 3, 5, 2];
findLeadersUsingFunctionalReduce(array1); //output: [17, 5, 2]
const array2 = [7, 10, 4, 3, 6, 5];
findLeadersUsingFunctionalReduce(array2); //output: [10, 6, 5]
const array3 = [2];
findLeadersUsingFunctionalReduce(array3); //output: [2]
const array4 = [];
findLeadersUsingFunctionalReduce(array4); //Throw error => Input must be a non-empty array
Reduce and Filter: Use reduceRight to accumulate maximum values and filter to find leaders.
Functional Style: Emphasizes functional programming paradigms.
Elegant and expressive using functional programming techniques.
Potentially less readable for those unfamiliar with functional patterns.
function findLeadersUsingSet(arr) {
if (!Array.isArray(arr) || arr.length === 0) {
throw new Error('Input must be a non-empty array');
}
const leaders = new Set();
let maxFromRight = arr[arr.length - 1];
leaders.add(maxFromRight);
for (let i = arr.length - 2; i >= 0; i--) {
if (arr[i] > maxFromRight) {
maxFromRight = arr[i];
leaders.add(maxFromRight);
}
}
return Array.from(leaders).reverse();
}
const array1 = [16, 17, 4, 3, 5, 2];
findLeadersUsingSet(array1); //output: [17, 5, 2]
const array2 = [7, 10, 4, 3, 6, 5];
findLeadersUsingSet(array2); //output: [10, 6, 5]
const array3 = [2];
findLeadersUsingSet(array3); //output: [2]
const array4 = [];
findLeadersUsingSet(array4); //Throw error => Input must be a non-empty array
Set Usage: Use a Set to track unique leaders and convert it to an array at the end.
Reversing: The result is reversed before returning.
Efficient with O(n) time complexity and unique leader tracking.
Uses a Set which might be less intuitive for some.
Finding leaders in an array can be useful in various scenarios such as:
Data Analysis: Identifying peak values or significant data points.
Algorithm Design: Enhancing understanding of algorithmic efficiency and optimization.
Competitive Programming: Solving algorithmic problems that involve array manipulation.
To find leaders in an array, use methods like single pass, brute force, stack, divide and conquer, functional programming (map/filter, reduce), helper arrays, or tracking with objects. Solutions provided cover diverse approaches for different needs.
The best method depends on your specific requirements:
Performance: If efficiency is a concern, methods like Single Pass, Stack, or Helper Array are optimal.
Simplicity: For a straightforward approach, the Brute Force method might be sufficient.
Functional Programming: If you prefer a functional programming style, consider methods using Map, Filter, or Reduce.
Memory Constraints: Methods using a stack or helper array require additional space, so choose accordingly based on memory limitations.
Yes, the core algorithms for finding leaders can be adapted to other programming languages like Python, Java, or C++. The syntax will differ, but the underlying logic remains the same.
The methods described work for arrays with negative numbers as well. The concept of a leader remains the same: an element is a leader if it is greater than all elements to its right, regardless of whether those elements are positive or negative.
The methods discussed are designed for one-dimensional arrays. For multidimensional arrays, you would need to flatten the array or apply similar logic to each dimension individually.
In a sorted array, the leaders are always the last elements in the array. For a non-decreasing sorted array, the only leader is the last element. For a non-increasing sorted array, all elements are leaders.