K Empty Slots


  • 1

    Click here to see the full article post


  • 0
    B

    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.


  • 0
    B

    Oh, i just looked at second solution looks like mine. Sry.


  • 0

    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


  • 0

    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.


  • 0

    @littlefinzer Thanks for bringing it to my attention. I will update the article in the next couple of days.


  • 0
    A

    The description/tests are inconsistent.
    There are problems with multiple answers, but the tests only accept one of them.

    Input: [3,9,2,8,1,6,10,5,4,7]
    1
    Output: 8
    Expected: 6

    //bloomTimes = 4 2 0 8 7 5 9 3 1 6
    //                 |___| |___|
    

  • 0

    @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.


  • 0
    C

    The third solution now is having time limit exceeded error


  • 0
    A

    Poorly written assignment with either invalid tests or description, like many stated above (A
    Ark-kun for ex)


  • 0
    A

    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.

    Input:
    [3,9,2,8,1,6,10,5,4,7]
    1
    Output:
    8
    Expected:
    6


  • 0

    @alexandr2017
    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)


  • 0
    Y

    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?


  • 0
    H

    I have got one test case failure says the correct answer for {6,5,8,9,7,1,10,2,3,4} k=2 is 8, shouldn't it be 7 ?
    after 7 days X X _ _ X X _ X X X , shed some light on this please.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.