Print Next Greater Number of Q Queries

Solution

The solution to the above problem is discussed below:

Normal Approach

A standard solution is for each query to go in a loop from index to n to print next greater number of q queries but this will take n iterations in the worst case, which is a lot if the number of searches is large.

Code:

// C++ program to print next greater number of Q queries

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	
	cout<<"Enter size of array\n";
	
	cin>>n;
	
	int a[n];
	
	cout<<"Enter the elements of array\n";
	
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	
	cout<<"Enter the number of queries\n";
	
	int q;
	
	cin>>q;
	
	cout<<"Enter the queries\n";
	
	for(int i=0;i<q;i++)
	{
		int query;
		cin>>query;
		int element = a[query];
		int temp=0;
		
		for(int j=query;j<n;j++)
		{
			if(a[j]>element)
			{
				// to print next greater number of q queries
				cout << "Next greater number to "<<query<<" is "<< a[j] << " \n";
				temp=1;
				break;
			}
		}
		
		if(temp==0)
		{
		cout << "Next greater number to "<<query<<" is "<< "-1" << " \n";
		}
	}
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Time Complexity: O(n^2)

Where n is the number of elements in the array.

Space Complexity: O(1)

Efficient Approach

To print next greater number of q queries we keep the index of the next greater element in an array, and for each query, we answer it in O(1), making it more efficient. There are two approaches to determining the next greater number for each index in an array.

One would need O(n^2) and O(n) space to loop from i+1 to n for each element at index i, finding and storing the next greater number. However, using stack, where we utilise indexes to compare and keep in next[] the next greater number index, will be more efficient.

Let us discuss the steps to implement the above approach.

1. Push the first index to the top of the stack.
2. Pick the remaining indexes and repeat the steps in a loop.
3. Mark the current element as i.
4. If the stack isn't empty, take an index from it and compare arr[index] to arr[I].
5. If a[i] is greater than the arr[index], arr[i] is the arr[index]'s next greater number.
6. Continue to pop index elements from the stack as long as the popped index element is smaller than arr[i]. arr[i] becomes the next greater number for all such popped elements.
7. If arr[i] is less than the popped index element, the popped index is pushed back.
8.  Pop all the indexes from the stack once the loop in step 2 ends and display -1 as the next index for them.

Code

The code for the efficient approach is given below:

// C++ program to print next greater number of q queries

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

// array to store the next greater element index
void next_greatest(int next[], int a[], int n)
{
	stack<int> s;

	// initialize the stack

	s.push(0);

	for (int i = 1; i < n; i++)
	{
		while (!s.empty()) 
		{
			// get the topmost index in the stack

			int cur = s.top();

			// If the current element is greater than the top indexth element, 
			// this will be the top indexth element's next largest index.

			if (a[cur] < a[i])
			{
				next[cur] = i;
				s.pop();
			}
			else
				break;
		}

		// push the i index so that its next greatest can be found

		s.push(i);
	}
		while (!s.empty())
		{
			int cur = s.top();

			// mark it as -1 as no
			// element in greater
			// then it in right

			next[cur] = -1;
			s.pop();
		}
}

int find(int a[], int next[], int n, int index)
{

	// stores the next greater element positions

	int position = next[index];

	// if position is -1 then no greater element is at right.

	if (position == -1)
	return -1;

	// if there is a index that has greater element at right then return its value as a[position]

	else
	return a[position];
}

// Driver Code

int main()
{
	int n;
    cout<<"Enter the size of the array \n";
    cin>>n;
    int arr[n];
    cout<<"Enter the elements of the array \n";
    
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    
    cout<<"Enter the number of queries \n";
    int q;
    cin>>q;
    
	// initializes the
	// next array as 0
	
	int next[n];
    memset(next,0,sizeof(next));

	// calls the function
	// to pre-calculate
	// the next greatest
	// element indexes
	
	next_greatest(next, arr, n);
    cout<<"Enter the queries \n";
    
	for(int i=0;i<q;i++)
    {
        int query;
        cin>>query;
        cout << "Next greater element to "<<query<<" is "<< find(arr, next, n, query) << " \n";
    }

	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Time Complexity: To print next greater number of q queries Time complexity is, O(1) for each query and O(n) for pre-processing the next[] array.

Auxiliary Space: O(n).

Where n is the number of elements in the array.

Check out this problem - Next Smaller Element

Frequently Asked Questions

What is a heap in data structure?

Heap is a balanced binary tree data structure in which the root-node key is compared to its offspring, and the data is sorted accordingly. A min-heap parent node has a lower key value than its children, whereas a max-heap parent node has a higher key value than its children.

What is hashing?

Hashing is a technique for converting a set of key values into a set of array indexes. We may use hash tables to establish an associative data storage where data indexes can be found by supplying their key values.

Define stack.

A stack is a container for added and deleted things using the last-in-first-out (LIFO) principle. Only two operations are permitted in pushdown stacks: pushing an item into the stack and popping an item out of the stack.

Stacks may be used to conduct three different tasks. They are as follows:

1. putting something in a stack (push).
2. Removing something from the stack (pop).
3. Displaying the stack's contents (peek or top).

What is a spanning tree?

Graph G is a subset of spanning trees with all vertices covered with the fewest number of feasible edges. There are no cycles in a spanning tree, and they cannot be severed.

Explain why the Stack data structure is recursive.

A stack is a recursive data structure because it is either empty or made up of a top and the remainder, which is a stack in and of itself.

Conclusion

In this article, we have extensively discussed the logic of how to print next greater number of q queries and then how to implement the logic in C++.

After reading about how to print next greater number of q queries, are you not feeling excited to read/explore more articles on the topic of DSA? Don't worry; Coding Ninjas has you covered. To learn, see the Problems of top tech companies for practice, Coding Interview Questions and Data Structures & Algorithms.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!