@Don: given stack will be 20 1 3 1 5 1 6 1 2 1
Minimum Stack will be 20 1 1 1 1 1
After pop 1
min stack 20 1 1 1 1
pop 2
min stack 20 1 1 1 1
pop 1
min stack 20 1 1 1
pop 6
min stack 20 1 1 1
pop1
min stack 20 1 1
pop 5
min stack 20 1 1
pop 1
min stack 20 1
pop 3
min stack 20 1
pop
Have a separate stack for minimum. While pushing, insert the number in
minimum stack only if the given number is less that or equal to the number @
the top of min stack. While removing, remove the value from min stack only
if its equal to the value thats popped.
--
You received this message
@HARISH:
Push 20 1 3 1 5 1 6 1 2 1
Pop
Now in your algorithm min will return 20, even though 1 and 3 and
other smaller numbers are still in the stack.
Don
On Sep 6, 6:25 am, HARISH S.C s.c.har...@gmail.com wrote:
Have a separate stack for minimum. While pushing, insert the number in
minimum
Guys What the Issue Here?? I think its straight forward.
If I hv two Stack
First :- Keep pushing and Popping the incoming values
Second :- Keeping track of the so far min element in the First Stack.
Now maintaining second stack is bit tricky.
PUSH :- If the element is
void push(int num){
if(stk1.isEmpty()){
stk1.push(num);
stk2.push(num);
}
else{
if(numstk2.top())stk1.push(num);
else{stk1.push(num);stk2.push(num)}
}
}
int pop(){
int num=stk1.pop();
if(num==stk2.top())stk2.pop();
return num;
}
On Tue, Sep
@ Shravan :- Thank for the Code but there are couple of issue with that..
1 Please try to provide the algo approach. Coz I feel
here we discuss irrespective of language , the technique of approach.
2 Your Code implementation of whatever your approach
is
@Shravan: Push can be written more compactly as
void push(int num)
{
stk1.push(num);
if(stk2.isEmpty() || num=stk2.top())
stk2.push(num);
}
Then don't forget min:
int min()
{
return stk2.top();
}
Dave
On Sep 6, 7:56 am, Shravan Kumar shrava...@gmail.com wrote:
void
@Prem: The approach has been discussed in previous posts in this
thread, so there is no need for Shravan to repeat it. Please follow
your own advice and tell what problem shows up with the sample input.
Dave
On Sep 6, 8:26 am, Prem Krishna Chettri hprem...@gmail.com wrote:
@ Shravan :- Thank
+1 sandeep
@don: u'r sol is correct , but if the number of elements are very huge and
the updated min is long numbers , then we are storing the min in each
element ... its waste of memory ...
if the # elements are less, then this is good sol..
On Mon, Sep 5, 2011 at 1:02 AM, Nitin Garg
+1 Don. Good Solution. We can't save space and time at the same time. Either
use extra space and do operations fast, or use O(1) for min, and if min is
popped, spend O(n) to spot the next min. Depends on the use case.
Karthik R,
RD Engineer,
Tejas Networks.
On Mon, Sep 5, 2011 at 5:10 PM,
In my earlier approach , if the element that is stored in min got popped
out then we have to search entire stack for min.. so i think my earlier
approach will not work.. tell me about that??
and i hav another approach.. also tell me about that also?
consider we have to push the elemnts 12
@sandeep
You don't need to store duplicate elements in stack2. When you want min
return top element. When an element is popped from stack1, pop stack2 only
if it is equal to popped stack1 element.
On Mon, Sep 5, 2011 at 8:21 PM, SANDEEP CHUGH sandeep.aa...@gmail.comwrote:
In my earlier
@Shravan: You at least have to push equal mins on the min stack.
Otherwise, with the sequence 2, 1, 1, if you push only 2 and 1 onto
the min stack, then when you pop the first 1 from the data stack and
pop the 1 from the min stack, the top of the min stack is 2, but the
minimum in the data stack
@dave : ya ryt..
@shravan ; my solution works for the case that dave has told.. so at every
step we hav to push min..
On Mon, Sep 5, 2011 at 9:11 PM, Dave dave_and_da...@juno.com wrote:
@Shravan: You at least have to push equal mins on the min stack.
Otherwise, with the sequence 2, 1, 1, if
@Dave agreed
@Sandeep it works, but it takes more memory
On Mon, Sep 5, 2011 at 9:15 PM, SANDEEP CHUGH sandeep.aa...@gmail.comwrote:
@dave : ya ryt..
@shravan ; my solution works for the case that dave has told.. so at every
step we hav to push min..
On Mon, Sep 5, 2011 at 9:11 PM, Dave
yeah memory will be a issue.. but if we want to use less memory.. then it
cannot be done in o(1)..
so the usual trade off space vs time... lol
On Mon, Sep 5, 2011 at 9:20 PM, Shravan Kumar shrava...@gmail.com wrote:
@Dave agreed
@Sandeep it works, but it takes more memory
On Mon, Sep 5,
@Shravan: Memory is cheep. $15 or less per gigabyte. When we are
talking about O(n), that allows n to get pretty large cheaply.
Dave
On Sep 5, 10:50 am, Shravan Kumar shrava...@gmail.com wrote:
@Dave agreed
@Sandeep it works, but it takes more memory
On Mon, Sep 5, 2011 at 9:15 PM, SANDEEP
@don :
say you have 10 elements and the min is also pointing to the Top of
stack..(1,3,2,4,5,6,7,3,5,2,7)
what would be the output of
pop() followed by min()
On Mon, Sep 5, 2011 at 9:37 PM, Dave dave_and_da...@juno.com wrote:
@Shravan: Memory is cheep. $15 or less per gigabyte. When we are
You can implement this by having each node in the stack keep track of the
minimum beneath itself.Then, to find the min, you just look at what the top
element thinks is the min.
When you push an element onto the stack, the element is given the current
minimum.It sets its “local min” to be the
@Teja: If I insert numbers in decreasing order, your solution will use
much more memory than just including the min in the same stack.
Also, what happens if I push the same minimum value several times? In
your solution, when the first one is popped off, that minimum value is
thrown out even though
Each element in the stack will contain not only its own value, but the
min value at that depth of the stack:
struct stackItemStruct
{
int value;
int min;
struct stackItemStruct *next;
};
typedef struct stackItemStruct stackItem;
class stack
{
public:
stack();
void push(int v);
int
Don's solution is correct.
At each push() operation, you update the value of min element upto that
depth in stack.
Can be illustrated with the following example -
stack = {}
push(2) stack = {(2,2)}
push(3) stack = {(3,2),(2,2)}
push(1) stack = {(1,1),(3,2),(2,2)}
where b in tuple (a,b)
22 matches
Mail list logo
