Leaders in an Array

Easy
476.

Leaders in an Array

Leaders in an Array is an easy coding problem on arrays, asked in Amazon, TCS and Accenture interviews.

An element of arr is a leader if it is greater than or equal to every element to its right. The rightmost element is always a leader.

Return all leaders in the order they appear in the array (left to right).

Example 1

Input
arr = [16,17,4,3,5,2]
Output
[17,5,2]
Explanation
17 beats everything to its right, 5 beats {2}, and 2 is last.

Example 2

Input
arr = [1,2,3,4,0]
Output
[4,0]

Example 3

Input
arr = [7,7,7]
Output
[7,7,7]
Explanation
Ties count — the comparison is >=.

Constraints

  • 1 <= arr.length <= 1000
  • 0 <= arr[i] <= 100000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number[]}
 */
var leaders = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Leaders in an Array — Solution in Python, Java & C++

Leaders in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays.

Leaders in an Array is an easy coding problem on arrays, asked in Amazon, TCS and Accenture interviews.

  • Difficulty: Easy
  • Topics: Arrays
  • Asked at: Amazon, TCS, Accenture
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

An element of arr is a leader if it is greater than or equal to every element to its right. The rightmost element is always a leader.

Return all leaders in the order they appear in the array (left to right).

Example 1

Input: arr = [16,17,4,3,5,2]
Output: [17,5,2]
Explanation: 17 beats everything to its right, 5 beats {2}, and 2 is last.

Example 2

Input: arr = [1,2,3,4,0]
Output: [4,0]

Example 3

Input: arr = [7,7,7]
Output: [7,7,7]
Explanation: Ties count — the comparison is >=.

Constraints

  • 1 <= arr.length <= 1000
  • 0 <= arr[i] <= 100000

Hints for Leaders in an Array

  1. Hint 1

    Comparing every element with all elements to its right is O(n²). What information does a right-to-left scan give you for free?

  2. Hint 2

    Walking backwards, the maximum of everything seen so far is the maximum of the suffix.

  3. Hint 3

    Collect leaders while scanning backwards, then reverse to restore the original order.

How to solve Leaders in an Array

A leader is an element that ties or beats the maximum of its suffix. Scanning right to left makes that suffix maximum a single running variable.

Approach

  1. Walk i from n - 1 down to 0, carrying best — the maximum of arr[i+1..n-1].
  2. If arr[i] >= best, record arr[i] as a leader and update best = arr[i].
  3. Reverse the collected list so it reads left to right.

Why it works

By induction, when index i is examined best already equals the suffix maximum, which is precisely the quantity the definition compares against. The last element trivially qualifies because its suffix is empty.

Complexity

  • Time — O(n)
  • Space — O(n) for the output

Pitfalls

  • Using > instead of >= drops duplicate leaders such as [7,7,7].
  • Forgetting the final reverse yields the leaders in right-to-left order.

Reference solution

Python

from typing import List

def leaders(arr: List[int]) -> List[int]:
    out = []
    best = -1
    for i in range(len(arr) - 1, -1, -1):
        if arr[i] >= best:
            out.append(arr[i])
            best = arr[i]
    out.reverse()
    return out

Java

public static int[] leaders(int[] arr) {
    int n = arr.length;
    int[] tmp = new int[n];
    int m = 0;
    int best = -1;
    for (int i = n - 1; i >= 0; i--) {
        if (arr[i] >= best) {
            tmp[m++] = arr[i];
            best = arr[i];
        }
    }
    int[] out = new int[m];
    for (int i = 0; i < m; i++) out[i] = tmp[m - 1 - i];
    return out;
}

C++

vector<int> leaders(vector<int>& arr) {
    vector<int> out;
    int best = -1;
    for (int i = (int) arr.size() - 1; i >= 0; i--) {
        if (arr[i] >= best) {
            out.push_back(arr[i]);
            best = arr[i];
        }
    }
    reverse(out.begin(), out.end());
    return out;
}

JavaScript

var leaders = function(arr) {
    const out = [];
    let best = -1;
    for (let i = arr.length - 1; i >= 0; i--) {
        if (arr[i] >= best) {
            out.push(arr[i]);
            best = arr[i];
        }
    }
    out.reverse();
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays