I already have the actual code. I just need the answers to 1 and 2 please. In th
ID: 3586285 • Letter: I
Question
I already have the actual code. I just need the answers to 1 and 2 please.
In this project, you will design and implement an algorithm to determine the next greater element of an element in an array in (n) time, where n' is the number of elements in the array. You could use the Stack ADT for this purpose. The next greater element (NGE) for an element at index i in an array A is the element that occurs at index j (i A[i]. If no such index j exists for an element at index i, then the NGE for the element A[i] is considered to be -1 For example: if an array is [1, 15, 26, 5, 20, 17, 36, 28), then the next greater element (NGE) of the elements in the array are as follows: 15 26 36 20 15 26 20 36 17 36 36 -1 28 -1 Note: Your code need not print the elements and their NGE values in the same order of the appearance of the elements in the array. An out of order print is also acceptable as long as the correct NGE for an element is printed out. For example, the following out of order print for the above array is also acceptable. 15 26 20 15 17 36 20 36 26 36 281 36 -1 You are given the doubly linked list-based implementation code for Stack along with this project description. Note that the main function in the code given to you already has the code snippet to generate an array of random elements. You just extend the main function to implement the algorithm. Submission (through Canvas): (1) Write a pseudo code of the algorithm designed and implemented for this problem. (2) Discuss the time complexity of the algorithm and justify that it is (n) with respect to the number of pop operations.Explanation / Answer
A)
Push the first element to stack.
For every other elements in the stack
Mark the current element as next.
If stack is not empty, then pop an element from stack and compare it with next.
If next is greater than the popped element, then next is the next greater element
for the popped element.
Keep popping from the stack while the popped element is smaller than next.
next becomes the next greater element for all such popped elements
If next is smaller than the popped element, then push the popped element back.
After the loop, pop all the elements from stack and print -1 as next element for them.
B)
Time Complexity - We push every element in the stack only once. So we pop every element only once and as there are only n elements in the array the complexity of the algorithm reduces to O(n) .
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.