Click here to see the full article post
Also, we can use somthing like bucket algorithm. Create buckets of k elements, and split all n values between this buckets. Each bucket should store min_left and max_right blooming index. So, at the beginning there are no blooming flowers in buckets. Each day we just set index in bucket (update values if it is needed). And check left and right bucket. O(n/k) additional memory and O(n) time.
To implement a min queue you can also use 2 stacks which is also amortized linear time. See https://stackoverflow.com/questions/4802038/implement-a-queue-in-which-push-rear-pop-front-and-get-min-are-all-consta
Can we add 1 more approach to an existing solution article? There's another way for sliding window but involves less steps than using a min queue.
@littlefinzer Thanks for bringing it to my attention. I will update the article in the next couple of days.
The description/tests are inconsistent.
There are problems with multiple answers, but the tests only accept one of them.
//bloomTimes = 4 2 0 8 7 5 9 3 1 6 // |___| |___|
@Ark-kun I think somewhere in the forum people already talked about this. You need to output the first day this event occurs, hence expected out put = 6 in your example.
Poorly written assignment with either invalid tests or description, like many stated above (A
Ark-kun for ex)
Or maybe my IQ is too low, but I am getting this, and we can't possible output 6 since day 8 didn't happen yet.
I really don't see why we need to output 6 if on day 6 this condition is not satisfied.
After 1st day:
_ _ X _ _ _ _ _ _ _
After 2nd day:
_ _ X _ _ _ _ _ X _
After 5th day:
X X X _ _ _ _ X X _
After 6th day:
X X X _ _ X _ X X _, satisfies the condition (theres K=1 unbloomed between bloomed at positions 6, 8)
For the sliding window approach, if
xrange is changed to
range then it gets TLE. This is in Python2. Anybody have an idea why there is such a difference?
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.