How to calculate Leaders in an Array

Leaders in an Array

Leaders in an array are those elements that are greater than the elements on their right-hand side in the array. This is by default true for the last element as the array end at that element and we can’t compare it with anyone.

Difficulty Level — Easy

Asked in — Microsoft and Adobe.

Let’s see an example to understand it better.

Example

Int[] arr = [16, 17, 4, 3, 5, 2]

Solution –

i=0 -> 16<17

16 is not a leader

i=1 -> 17>4, 17>3, 17>5, 17>2

17 is a leader

i=2 -> 4>3, 4<5

4 is not a leader

i=3 -> 3<5

3 is not a leader

i=4 -> 5>2

5 is a leader

i=5 -> 2 — end of the array which makes it a leader as well

Thus the leaders of the array [16, 17, 4, 3, 5, 2] are 17, 5, 2.

Observations

  1. The last element of the array is the leader by default
  2. The same goes for the largest element of the array
  3. Ordering doesn’t matter

How to solve it.

There are two possible methods of solving it — the brute force approach and max from the right. The brute force approach will give us a time complexity of O(n2) while the other one will give us a time complexity of O(n) — an efficient approach.

In this blog, we will use and understand both of these methods to solve this question.

Approach — I — Brute Force

As the question said, we have to find the element greater than all the elements on its right-hand side. So the brute force should be to check for all the elements if there exists an element greater than the chosen element in the array specifically on the right-hand side.

The first thing that came to mind is to use a double loop system (nested) in which the outer loop will take an element and compare it with the other elements of the array using the second or the inner loop.

Below is the Pseudo Code and the actual code for the above-discussed approach.

Continue Reading.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Ateev Duggal

I am a front-end developer from India with over one year of experience in freelancing with skills like Git, HTML5, CSS3, Bootstrap 4&5, and React.