Leaders in an Array

Problem Statement

Solution 1: Find Leaders Using a Single Pass

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 

Solution 2: Find Leaders Using Brute Force Approach

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 

Solution 3: Find Leaders Using a Stack

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 

Solution 4: Leaders in an array solution Using Divide and Conquer

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 

Solution 5: Find Leaders Using Functional Programming (Map and Filter)

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 

Solution 6: Using a Helper Array

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 

Solution 7: Using an Object to Track Maximums

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 

Solution 8: Using Functional Programming (Reduce and Filter)

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 

Solution 9: Using JavaScript Set

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 

Resources

Frequently asked questions

1. Why is it important to find leaders in an array?

   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.

2. How to find leaders in an array

   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.

3. How do I choose the best method to find leaders in an array?

   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.

4. Can I use these methods in other programming languages?

   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.

5. What should I do if the array contains negative numbers?

   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.

6. Can these methods be used with multidimensional arrays?

   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.

7. What if I want to find leaders in a sorted array?

   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.

More Problems Solutions