Subscribe to:
Post Comments (Atom)
About Me
- sagopal
- A fun loving individual particularly a foodie and a tech savvy in my career. Thankful to God, who has treated me so far so good,touchwood. I am interested to ('share with'/'help'/'get help from') my readers especially on the lines of "places of interest","Software Technology","Indian Cusine", "Entertainment","Travel","Making Friends","Career advice","Product Reviews" You can also contact me at sagopal@gmail.com
Cornify
PageViews
4 comments:
maintain another stack min[n]. when ever you insert an element in the original stack, insert the index of the min element at that point.
So at any given point you want to take the min element, goto min stack, get the index value and fetch the element.
Stack
45
78
38
67
50
minStack
2
2
2
0
0
@vijesh,
Thats a nice solution.
Assuming that a stack is not an array , in which case getting the index value and fetching the element at index wont work , can you devise or slightly modify your answer to arrive at a better solution ?
I agree that getting an element in a array knowing the index is O(1).
Also could you please talk about the pop() operation?
maintain two stacks one stack(input stack) is for storing the incoming numbers and the second stack(minimum stack) is for holding the minimum number.
Assume the input sequence is 8,2,9,5,10
when u get a number to push into 'input stack' , In case if its the first element to be pushed inside the 'input stack' just push it into 'minimum stack' otherwise check whether that number is less than the top of 'minimum stack' if its less push that number into 'minimum stack' also else push it into 'input stack' alone.
When u pop the number from the 'input stack' , check whether the top of the 'input stack' and 'minimum stack' are equal if they are equal pop from both that stacks else pop from 'input stack' alone.
Now the top of the 'minimum stack' contains the minimum number of 'input stack'.
Eg:
input sequence : 8,2,9,5,10,1
push operations :
input stack - 8
minimum stack - 8
input stack - 2 , 8
minimum stack - 2, 8
input stack - 9 , 2 , 8
minimum stack - 2 , 8
input stack - 5, 9 , 2 , 8
minimum stack - 2 , 8
input stack - 10 , 5, 9 , 2 , 8
minimum stack - 2, 8
input stack - 1, 10 , 5, 9 , 2 , 8
minimum stack - 1, 2, 8
minimum number :
top of 'minimum stack' , which is '1'.
pop operation:
If we pop the '1' from the 'input stack' we will pop '1' from 'minimum stack' also as top of stack of both the stacks are the same , now '2' will be the minimum number.
pop '1' :
input stack - 10 , 5, 9 , 2 , 8
minimum stack - 2, 8
pop '10'
input stack - 5, 9 , 2 , 8
minimum stack - 2, 8
pop '5'
input stack - 9 , 2 , 8
minimum stack - 2, 8
Minimum number :
Now the minimum of 'input stack' is 2 , which is the top of 'minimum stack'.
Nice solution at http://www.rawkam.com/?p=1337
Post a Comment