Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Arrays

Leaders in an Array

Easy · Arrays · Asked at Amazon, Adobe, TCS, Infosys

An element is a leader if it is strictly greater than every element to its right. The last element is always a leader. Print all leaders from left to right.

Input

First line: n. Second line: n space-separated integers.

Output

The leaders, space-separated, in their original order.

Constraints

Scan from the right while tracking the maximum seen so far.

Example 1

Input

6
16 17 4 3 5 2

Output

17 5 2

Example 2

Input

3
1 2 3

Output

3

Hints

  1. Checking everything to the right of each element is O(n²).
  2. Scan from the right, tracking the maximum so far. An element is a leader if it is bigger than that maximum.

Approach

Walk from the last element to the first with maxRight (start below every value). If a[i] > maxRight, a[i] is a leader; then update maxRight. Leaders are found right-to-left, so reverse them before printing.

Complexity: O(n) time · O(n) space for the output

Solution

C++ solution

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

int main() {
    int n;
    cin >> n;
    vector<long long> a(n), leaders;
    for (auto &x : a) cin >> x;
    long long maxRight = LLONG_MIN;
    for (int i = n - 1; i >= 0; i--) {
        if (a[i] > maxRight) leaders.push_back(a[i]);
        maxRight = max(maxRight, a[i]);
    }
    reverse(leaders.begin(), leaders.end());
    for (size_t i = 0; i < leaders.size(); i++) cout << leaders[i] << (i + 1 < leaders.size() ? " " : "\n");
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
a = data[1 : data[0] + 1]
leaders, max_right = [], float("-inf")
for x in reversed(a):
    if x > max_right:
        leaders.append(x)
    max_right = max(max_right, x)
print(*reversed(leaders))

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        List<Long> leaders = new ArrayList<>();
        long maxRight = Long.MIN_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            if (a[i] > maxRight) leaders.add(a[i]);
            maxRight = Math.max(maxRight, a[i]);
        }
        Collections.reverse(leaders);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < leaders.size(); i++) sb.append(i > 0 ? " " : "").append(leaders.get(i));
        System.out.println(sb);
    }
}

Solve Leaders in an Array online · All practice problems