RUN


Given: An array, we have to print the next greater element for each element. The Next greater Element for an element p is the first greater element on the right side of p in array. Elements for which there is no greater element, we consider next greater element as -1.  

Example:

Input array: { 37, 23, 64, 10, 25, 7 }
Output:
Next greater element for 37     = 64
Next greater element for 23     = 25
Next greater element for 64     = -1
Next greater element for 10     = 23
Next greater element for 25     = 37
Next greater element for  7      = 10

 

# Brute Force Approach 

Code:

#include <iostream>

// prints NGE for all elements of array[]  

void nextgren(int array[], int size)

{
	int next;

	for (int i = 0; i < size; i++)

	{

		next = -1;

		for (int j = i + 1; j < size; j++)

		{

			if (array[i] < array[j])

			{

				next = array[j];

				break;
			}
		}

		std::cout << "Next greater element for " << array[i] << " = " << next << std::endl;
	}
}

// Driver Code

int main()

{

	int array[] = { 5, 4, 7, 15 };

	int size = sizeof(array) / sizeof(array[0]);

	nextgren(array, size);

	return 0;

}

Time Complexity: O(n2).

# Optimised Approach(Using Stack)

Code:

// C++ program to find next greater element using stack
#include <bits/stdc++.h>

// prints NGE for all elements of array

void nextgren(int array[], int size)

{

	std::stack<int> stck;

	// push first element to stck 

	stck.push(array[0]);

	// iterating for next elements

	for (int i = 1; i < size; i++)

	{

		if (stck.empty())

		{

			stck.push(array[i]);

			continue;
		}

		/*if stck is not empty, then pop an element from stck.

    If the popped element is smaller than next, then
    1) print the element and next
    2) keep popping while elements are smaller and stck is not empty */

		while ((stck.empty() == false) && (stck.top() < array[i]))

		{

			std::cout << "Next greater element for " << stck.top() << " = " << array[i] << std::endl;

			stck.pop();
		}

		// push next to stck so we can find next greater for it

		stck.push(array[i]);
	}

	/*After iteration is over, the remaining

	elements in stck do not have the next greater

	element, so we print -1 for them */

	while (stck.empty() == false)

	{

		std::cout << stck.top() << " --> " << -1 << " (No greater element in given input) " << std::endl;

		stck.pop();
	}
}

// Driver code

int main()

{

	int array[] = { 6, 10, 12, 9 };

	int size = sizeof(array) / sizeof(array[0]);

	nextgren(array, size);

	return 0;

}

Time Complexity: O(n).

 

Report Error/ Suggestion

Related Posts:





CopyRight © 2020

CopyRight © 2020