For using a stack in order to achieve O(n) time, we can modify push and pop
as follows(assuming we want max):
While pushing, compare the top of the stack with the element to be
pushed(say x). If xtop, just push normally. Else, pop elements until
topx. Keep an eye on the border cases as well. Thus
steps:
1) make max heapify and min heapify for first k days
2)for the next day... remove first element from max heapify and min
heapify then add new element to existing max heapify and min
heapify .
3) Then return max and min in O(1)from max heapify and min heapify .
PRAVEEN RAJ
DELHI
can you please elaborate on usage of stack to do it in O(1)?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/8jTvBVdzsmYJ.
To post to this group, send email
Min or max heap accordingly. This will do the job in O(log n) time.
On Sun, Jul 15, 2012 at 1:25 AM, Navin Kumar algorithm.i...@gmail.comwrote:
A set of integer values are being received (1 per day). Store these values
and at any given time, retrieve the min and max value over the last k days.
It says K days if you keep heap the order of values gets disturbed. How are
last k values accessed then?
On Sunday, 15 July 2012 12:46:02 UTC+5:30, adarsh kumar wrote:
Min or max heap accordingly. This will do the job in O(log n) time.
On Sun, Jul 15, 2012 at 1:25 AM, Navin Kumar
I think stack would solve the purpose. please comment.
On Sun, Jul 15, 2012 at 5:42 PM, enchantress elaenjoy...@gmail.com wrote:
It says K days if you keep heap the order of values gets disturbed. How
are last k values accessed then?
On Sunday, 15 July 2012 12:46:02 UTC+5:30, adarsh kumar
Oh ya sorry. I thought we have to retrieve kth min and max, in which case
heap can be used.
Here, we can either use stack or map. Map can be from a date(which
increases by 1 daily) to a value, as only one value is received per day.
Keeping in mind memory constraints, stack is better. Map is an
I think by using min/max heap we can fetch the kth largest/smallest data
from the heap. But here there is one more point how to ensure that the data
is smallest in last kth day. Here you can use interval/segment(augmented
version of heap tree) tree, where u can store the interval/segment on the
agree with naveen
On Sun, Jul 15, 2012 at 6:24 PM, Navin Kumar algorithm.i...@gmail.comwrote:
I think stack would solve the purpose. please comment.
On Sun, Jul 15, 2012 at 5:42 PM, enchantress elaenjoy...@gmail.comwrote:
It says K days if you keep heap the order of values gets disturbed.
Stack will do it...
and min or max can be even retrieved in O(1) ...
On Sun, Jul 15, 2012 at 6:36 PM, adarsh kumar algog...@gmail.com wrote:
Oh ya sorry. I thought we have to retrieve kth min and max, in which case
heap can be used.
Here, we can either use stack or map. Map can be from a
10 matches
Mail list logo
