Leaders in an Array. DSA #2

Question

Think of a solution with the help of an example

First I will discuss Brute force method

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

Is 16 a leader, no because 17 is greater than 16
Is 17 a leader, Yes because it is greater than all the element in it's right
Is 4 a leader, no because of 5.
Is 3 a leader, no because of 5.
Is 5 a leader, Yes because it is greater than all the element in it's right.
Is 2 a leader, Yes because there is no element in it's right so it is obviously greatest.

From this thinking process, we can see two things.

1. The last number will always be the leader.
2. If we take a number and compare it with every number which comes after it we can easily find out which number is the leader.

This will require 2 loop.
First loop will take a particular number.
Second loop will compare it with all the numbers after it. To check if it is greater than all the number.

Let's test our theory.
arr = [16, 17, 4, 3, 5, 2]

let's take 16
Is 16 greater than 17 -> False. Therefore we break out of the loop.
let's take 17.
Is 17 greater than 4 -> True.
Is 17 greater than 3 -> True.
Is 17 greater than 2 -> True.
Is 17 greater than 5 -> True.
Is 17 greater than 2 -> True.

We didn't break out of the loop. Therefore 17 is the leader.
And we will continue this process till the outer loop terminates.

Code for the above approach

vector<int> findLeader(int arr[], int n){

     // For storing the result
    vector<int> ans;

    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(arr[i] < arr[j]){
                break;
            }
        }
    }
    return ans;

}

but this code is not complete because we are not storing the leader in ans anywhere in the code. So where we should add the statement to store leaders in the ans.

The answer is very simple if we ask one question to ourself.

When we need to add the numbers in the ans?

When the loop is not break. And to know this we can simply add the variable in our code whose value we will change when the loop breaks. And in the end we can simply check if the value of the variable is changed or not. If it is not changed we add the number to the ans.

Final code.

vector<int> findLeader(int arr[], int n){
    vector<int> ans;
    int flag;
    for(int i = 0; i < n; i++){
// Always set to 0 for new value
        flag = 0;
        for(int j = i + 1; j < n; j++){
            if(arr[i] < arr[j]){
// value is changed
                flag++;
                break;
            }
        }
// If value is not changed
        if(flag == 0){
            ans.push_back(arr[i]);
        }
    }
    return ans;

}

Better approach

Think like this leader is those numbers which are greater than all the numbers in there right so why don't we start our loop from the right and keep track of the max. If the current number is greater than the max then we can say that it is a leader. Let's understand this approach with the help of an example.

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

current window = [2]
since last element is always leader we add 2 to our res and current max in the window is 2.

current window = [5, 2]
Is 5 is greater than the current max (2) -> True. Therefore we can say it is greater than all the elements on it's right because it is greater than the max in it's right. We add 5 to our res. Current max in the window is 5.

current window = [3, 5, 2]
Is 3 is greater than the current max (5) -> False. Which means 3 can't be a leader because it is smaller than 5 which falls on it's right side.

current window = [4, 3, 5, 2]
Is 4 is greater than the current max (5) -> False. Which means 4 can't be a leader because it is smaller than 5 which falls on it's right side.

current window = [17, 4, 3, 5, 2]
Is 17 is greater than the current max (5) -> True. Therefore we can say it is greater than all the elements on it's right because it is greater than the max in it's right. We add 17 to our res. Current max in the window is 17.

current window = [16, 17, 4, 3, 5, 2]
Is 16 is greater than the current max (17) -> False. Which means 16 can't be a leader because it is smaller than 17 which falls on it's right side.

Loop will end and our res will contain = [2, 5, 17]

To code this problem we need two variables
First variable should point to the current max element in the right side.
Second pointer should point to the new element which we want to check for the leader

Code for the above approach

vector<int> findLeader2(int arr[], int n){
    // Since last element is always a leader  
    vector<int> res = {arr[n - 1]};
    int 
        i = n - 1,   // first pointer which will point to the current max
        j = i - 1;   // Second pointer which will point to new element to check for leader

    while (j >= 0){
        if(arr[j] >= arr[i]){
            res.push_back(arr[j]);
            // Pointer 1 is set to the new current max
            i = j;
        }
        j--;
    }
        // To return the number in order.
        reverse(res.begin(), res.end());
        return res;
}

Let's Dry run the above code

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

res = [2]
i = 5
j = 4
------First iteration---------

Is 5 > 2 ---> True.
res = [2, 5]
i = 5 ( i should always point to the max in the current window)
j = 3

------Second iteration---------

Is 3 > 5 ---> False.
res = [2, 5]
i = 5
j = 2

------Third iteration---------

Is 4 > 5 ---> False.
res = [2, 5]
i = 5
j = 1

------Fourth iteration---------

Is 17 > 5 ---> True.
res = [2, 5, 17]
i = 17
j = 0

------Fifth iteration---------

Is 16 > 17 ---> False.
res = [2, 5, 17]
i = 5
j = -1

Loop terminates

After reversing res = [17, 5, 2]