RUN


PROBLEM: Print all the LEADERS in the array. An element is a leader if it is greater than the elements to its right in the array.

Input: [32, 2, 4, 2, 5, 17, 24, 22]

Output: [32, 34, 22]

# Brute Force

Pseudo Code:

  1. We start a loop and iterate till the second last element.
  2. Inside another loop, we iterate over elements to its right( to the last index) to check if it is a leader
  3. If it is greater than all elements, we mark it as a leader.
  4. The rightmost is added after the loop ends.

Code:

#include <iostream>
using namespace std;

void printLeader(int arr[], int size)
{
	for (int iterator = 0; iterator< size; iterator++)
	{
    	int innerIterator;

		for (innerIterator = iterator + 1; innerIterator < size; innerIterator++)
		{
			if (arr[iterator] <= arr[innerIterator])
				break;
		}

		if (innerIterator == size)
			cout << arr[iterator] << " ";
	}
}

int main()
{
	int arr[] = { 32, 2, 4, 2, 5, 17, 24, 22 };
	cout << "Leaders are { ";
	printLeader(arr, 8);
	cout << "}";
	return 0;
}

Output:

Leaders are { 32, 24, 22 }

Time Complexity: O(N*N)

Space Complexity: O(1)

 

# Optimized Approach

Pseudo Code:

  1. We start a loop from the right.
  2. We keep checking the max value. As soon as a max is found, print it.
  3. End.

Code:

#include <iostream>
using namespace std;

void printLeadersOptimized(int arr[], int size)

{
	int maxRight = arr[size - 1];
	cout << maxRight << " ";
	for (int iterator = size - 2; iterator >= 0; iterator--)
	{
		if (maxRight < arr[iterator])
		{
			maxRight = arr[iterator];
			cout << maxRight << " ";
		}
	}
}

int main()
{
	int arr[] = { 32, 2, 4, 2, 5, 17, 24, 22 };
	cout << "Leaders are { ";
	printLeadersOptimized(arr, 8);
	cout << "}";
	return 0;
}

Output:

Leaders are { 32, 24, 22 }

Time Complexity: O(N)

Space Complexity: O(1)

 

Report Error/ Suggestion

Related Posts:




CopyRight © 2020

CopyRight © 2020