Leaders in an array

Easy
0/40
Average time to solve is 15m
profile
Contributed by
73 upvotes
Asked in companies
AdobeQuikrMicrosoft

Problem statement

Given a sequence of numbers. Find all leaders in sequence. An element is a leader if it is strictly greater than all the elements on its right side.

Note: 
1. Rightmost element is always a leader.

2. The order of elements in the return sequence must be the same as the given sequence
Example: 
The given sequence is 13, 14, 3, 8, 2 .

13 Not a leader because on the right side 14 is greater than 13.

14 lt is a leader because no one greater element in the right side.

3 Not a leader because on the right side 8 are greater than 3.

8 It is a leader because no one greater element on the right side.

2 It is a leader because it is the rightmost element in a sequence.

Hence there are 3 leaders in the above sequence which are 14, 8, 2.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains an integer ‘N’ denoting the number of elements in the given sequence. 

The second line of each test case contains ‘N’ space-separated integers denoting the elements in the sequence.
Output Format: 
For each test case, print a sequence of all leaders separated by space on a separate line.
Note: 
You don't need to print anything, it has been already taken care of. Just implement the given function.
Constraints: 
1 <= T <= 50
1 <= N <= 10^4
-10^9 <= ELEMENTS[i] <= 10^9

Where ‘ELEMENTS[i]’ denotes an element at position ‘i’ in the sequence.

Time limit: 1 sec
Sample Input 1:
2
6
6 7 4 2 5 3
4
11 10 9 8
Sample Output 1:
7 5 3
11 10 9 8
Explanation of Sample Output 1:
In test case 1,

6 Not a leader because on the right side 7 is greater than 6.

7 lt is a leader because no one greater element in the right side.

4 Not a leader because on the right side 5 are greater than 4.

2 Not a leader because on the right side 5, 3 are greater than 2.

5 lt is a leader because no one greater element in the right side.

3 It is a leader because it is a rightmost element in a sequence.

Hence there are 3 leaders in sequence 7, 5, 3. 

In test case 2,

Given sequence is in descending order, so all elements are leaders
Sample Input 2:
2
6
5 10 11 12 -1 -2
4
10 -11 -3 -2
Sample Output 2:
12 -1 -2
10 -2
Explanation of Sample Output 2:
In test case 1,

5 Not a leader because on the right side 10 is greater than 5.

10 Not a leader because on the right side 11 is greater than 10.

11 Not a leader because on the right side 12 are greater than 11.

12 lt is a leader because no one greater element in the right side.

-1 lt is a leader because no one greater element in the right side.

-2 It is a leader because it is a rightmost element in a sequence.

Hence there are 3 leaders in sequence 12, -1, -2. 

In test case 2,

10 lt is a leader because no one greater element in the right side.

-11 Not a leader because on the right side -3 are greater than -11.

-3 Not a leader because on the right side -2 are greater than -3.

-2 It is a leader because it is a rightmost element in a sequence.

Hence there are 2 leaders in sequence 10, -2.
Hint

Try checking for one element at a time if it is a leader.

Approaches (2)
Brute Force

The steps are as follows:

 

  • We use two loops.
  • The outer loop runs from left to right of the sequence using a variable INDEX’, and in a single instance of the iteration ‘INDEX’ will represent the index of each element of the sequence.
  • The inner loop runs from ‘INDEX + 1’ to the end of the sequence using a variable ‘rightIndex’, in which ‘rightIndex’ will point to the element that is on the right side of the element and will be picked by the outer loop.
  • If element picked by the outer loop is greater than all the elements of picked by inner loop then element picked by the outer loop is the leader.
  • Finally, return the answer sequence.
Time Complexity

O(N ^ 2), Where ‘N’ is the size of a given sequence.

 

Since for each of the N element, we iterate through the whole sequence (N times in worst case). Thus the time complexity will be O(N ^ 2).

Space Complexity

O(M), Where ‘M’ is the size of our ‘ANSWER’ sequence.

 

Since the ‘ANSWER’ sequence is a sequence in which we store all the elements which are a leader.

Code Solution
(100% EXP penalty)
Leaders in an array
Full screen
Console