amber
BAN USERI am assuming you gave the solution by finding the height and then
calling the print function for each level.
The complexity is O(n logn) assuming there are n levels.
because at every iteration you are going to a particular level which is (log n)
and you are doing this for n levels
Start from right to left keeping track of maximum.
arr = [4, 45, 2, 25]
barr= [45,25,25,-1] // new array that gives next greatest element
let length of array be n
b[n-1] = -1; // as there is no next greatest
int temp = arr[n-1]
for (i=n-2; i>=0; i--)
{
barr[i] = temp;
if(arr[i] > temp)
{
temp = arr[i];
}
}
use another stack to keep track of minimum
stack 1 : stack 2:
push 2 push 2
stack 1: stack 2:
push 4 dont do anything
stack 1: stack 2:
push 1 push 1
Stacks contain the following:
stack 1: 1 4 2
stack 2: 1 2
When we pop from S1 check if it is equal to top of stack 2, if so pop from both stacks
Could you please give an example ?
- amber October 28, 2013