Hi Guys
A more space efficient solution is here
push(x)
{
if stack.empty()
{
stack.push(x);
stack.push(x);
}
else
{
if x > stack.top()
{
min = stack.pop()
stack.push(x)
stack.push(min)
}
else
Dave, we don't remove (3,3)...
min_query will return 3 stored at the top..ie (9,3)..
pop will remove (9,3).. not (3,3)
On Thu, Oct 8, 2009 at 8:47 PM, sharad kumar wrote:
> 3 is min element then y to return 5??if u remove 9,3
> 3 at tos 3 is min so y to remove 5 borther dave
>
> On Thu, Oct 8,
3 is min element then y to return 5??if u remove 9,3
3 at tos 3 is min so y to remove 5 borther dave
On Thu, Oct 8, 2009 at 8:37 PM, Dave wrote:
>
> Satyam, let's work your example in detail. We've pushed your data onto
> the stack, and now we start popping.
>
> (6,6),(5,5),(10,5),(3,3),(9,3),(
Satyam, let's work your example in detail. We've pushed your data onto
the stack, and now we start popping.
(6,6),(5,5),(10,5),(3,3),(9,3),(1,1), so remove the (1,1) and return
1.
(6,6),(5,5),(10,5),(3,3),(9,3) so remove (3,3) and return 3.
(6,6),(5,5),(10,5),(9,3). Now what? How do we find (5,5)
@harit
o..Got it now.
Thanks a lot for detailed explanation.
On Oct 8, 4:15 pm, harit agarwal wrote:
> @manisha
> i think u didn't get my point
>
> every time it will return the different value
> ex
> values to be pushed 6,5,10,3,9,1
> now push(a,b) a=element b=minimum value pushed till no
@manisha
i think u didn't get my point
every time it will return the different value
ex
values to be pushed 6,5,10,3,9,1
now push(a,b) a=element b=minimum value pushed till now
(6,6)
(6,6),(5,5)
(6,6),(5,5),(10,5)
(6,6),(5,5),(10,5),(3,3)
(6,6),(5,5),(10,5),(3,3),(9,3)
(6,6),(5,5),(10,5),(3,3),(9,
Try maintaining at every node in the queue the minimum till that node
in addition to the value.
min() will return the min val stored at the top.
On Thu, Oct 8, 2009 at 9:22 AM, Manisha wrote:
>
>
>
> @harit
>
> Maintaining only one data member, minimum will not suffice. As we may
> call min() an
@harit
Maintaining only one data member, minimum will not suffice. As we may
call min() any number of time and every time it should return the
minimum of all data members.
@sharad
Thanks for direction.
In your implementation, stack.top() and stack.pop() are going to
return same value.
So min()
question is just to retrieve minimum element and not to do any operation
like push pop on it
so do one thing push the element on stack with one more data member that
contains minimum number seen till now...that will be enough[?]
--~--~-~--~~~---~--~~
You receive
The basic idea would be to do push / pop the minimum in stack along with the
push / pop elements. It is like maintaining a parallel stack of minimums. A
naive implementation would involve two stacks. All operations should be O(1)
time complexity.
On Tue, Oct 6, 2009 at 1:31 PM, Manisha wrote:
>
brother try this
push(x)
{
if stack.empty()
{
stack.push(x);
stack.push(x);
}
else
{
if x > stack.top()
{
min = stack.top()
stack.push(x)
stack.push(min)
}
else
{
stack.push(x
11 matches
Mail list logo
