Find the Leader

Last Updated on March 28, 2022 by Ria Pathak

CONCEPTS USED:

Basic Mathematics

DIFFICULTY LEVEL:

Medium

PROBLEM STATEMENT(SIMPLIFIED):

Print all those elements that have no element greater than them in the right side of the array. Print elements from right to left.

See original problem statement here

For Example:

Input : A[] = [1, 2, 3, 4, 5]

Output : 5

Explanation : Only 5 has no element greater than it on its right.

Input : A[] = [1, 4, 3, 2]

Output : 2 3 4 

Explanation : 2, 3, and 4 have no elements greater than them on their right while 1 has 4, 3 and 2 greater than it on its right.

SOLVING APPROACH:

BRUTE FORCE METHOD:

1. Run two nested loops, outer loop for selecting an element and inner loop for picking each element one by one on its right and checking if the selected element is not less than the picked element. After running one complete inner loop, if the selected element was not less than any of the picked element, print its value else move ahead.

2. Outer loop will run from right to left as we need to print elements from the right.

3. Time Complexity of this solution is O(N²).

SOLUTIONS:

#include <stdio.h>

int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
    int n;
    scanf("%d",&n);
    int arr[n];
    for(int i=0;i<n;i++)
      scanf("%d",&arr[i]);
    for(int i=n-1;i>=0;i--)
    {
      int flag=0;
      for(int j=i;j<n;j++)
      {
        if(arr[i]<arr[j])
        {
          flag=1;
          break;
        }
      }
      if(flag==0)
      {
        printf("%d ",arr[i]);
      }
    }
    printf("\n");
  }
  return 0;
}

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

int main()
{
  int t;cin>>t;
  while(t--)
  {
    int n;cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
      cin>>arr[i];
    for(int i=n-1;i>=0;i--)
    {
      int flag=0;
      for(int j=i;j<n;j++)
      {
        if(arr[i]<arr[j])
        {
          flag=1;
          break;
        }
      }
      if(flag==0)
      {
        cout<<arr[i]<<" ";
      }
    }
    cout<<"\n";
  }
  return 0;
}

Time Complexity: O(N²)
Space Complexity: O(1)

EFFICIENT METHOD:

1. The idea is to traverse the array from the right, as the rightmost element will be our first leader as there are no elements present at the right of it.

2. Print the element and store the element as the largest element.

3. Now traverse the array from Right to Left and check if the value of current element is greater than the largest value, if YES then it is also the leader. Simply print this value and update the largest value. If NO, move ahead.

4. Repeat steps 2 and 3 until the entire array is traversed.

ILLUSTRATION:

A[] = [1, 4, 3, 2]
Max = -1

i = n - 1 = 3
A[i] > Max (2 > -1)
Max = A[i] => Max = 2
i-- 
print A[i]

i = 2
A[i] > Max (3 > 2)
Max = A[i] => Max = 3
i-- 
print A[i]

i = 1
A[i] > Max (4 > 3)
Max = A[i] => Max = 4
i-- 
print A[i]

i = 0
A[i] < Max (1 < 4)
i--

i = -1
return 

We have successfully printed all values that have no greater values than them in their right.

SOLUTIONS:

#include <stdio.h>

int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
    int n;
    scanf("%d",&n);
    int arr[n];
    for(int i=0;i<n;i++)
      scanf("%d",&arr[i]);
    int largest = arr[n-1];
    printf("%d ",arr[n-1]);
    for(int i=n-2;i>=0;i--)
    {
      if(arr[i]>=largest)
      {
        largest = arr[i];
        printf("%d ",arr[i]);
      }
    }
    printf("\n");
  }
  return 0;
}

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

int main()
{
  int t;cin>>t;
  while(t--)
  {
    int n;cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
      cin>>arr[i];
    int largest = arr[n-1];
    cout<<arr[n-1]<<" ";
    for(int i=n-2;i>=0;i--)
    {
      if(arr[i]>=largest)
      {
        largest = arr[i];
        cout<<arr[i]<<" ";
      }
    }
    cout<<"\n";
  }
  return 0;
}

import java.util.*;
import java.io.*;

public class Main {
  public static void main(String args[]) throws IOException {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while(t!=0)
    {
      int n = sc.nextInt();
      int arr[] = new int[n];
      for(int i=0;i<n;i++)
        arr[i] = sc.nextInt();
      int largest = arr[n-1];
      System.out.print(arr[n-1] + " ");
      for(int i=n-2;i>=0;i--)
      {
        if(arr[i]>=largest)
        {
          largest = arr[i];
          System.out.print(arr[i] + " ");
        }
      }
      System.out.println("");
      t--;
    }
  }
}

[forminator_quiz id="490"]

This article tried to discuss Basic Mathematics. Hope this blog helps you understand and solve the problem. To practice more problems on Basic Mathematics you can check out MYCODE | Competitive Programming.