3

This question is a variant of k empty slot from leetcode. the new question is, ask to find the last day when there are k consecutive bloomed flowers.

e.g. total 7 days, 1 represents flower bloomed，0 represents flower not bloomed, k=3

day1：1 0 0 0 0 0 0

day2：1 0 1 0 0 0 0

day3：1 1 1 0 0 0 0 1st time find k consecutive bloomed flowers

update: lastDayBloomKflowers = 3

day4：1 1 1 0 1 0 0

day5：1 1 1 0 1 1 0

day6：1 1 1 0 1 1 1 2nd time find k consecutive boomed flowers

update: lastDayBloomKflowers = 6

day7：1 1 1 1 1 1 1

finally, flowers will bloom at all position

so the final solution is lastDayBloomKflowers = 6

how can we get lastDayBloomKflowers? the time complexity is O(nlogn), space is O(n)

I know how to solve the original leetcode question, I would like to use tree set, but for this variant, I have no idea what data-structure I should use, and efficiently solve it.

Thank you for your time!

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

I am asking for help for the variant of k empty slot problem.

Since the url for k empty slot problem on leetcode is for prime number, and some of you guys may not able to open, I will show you original k empty slot problem here:

There is a garden with N slots. In each slot, there is a flower. The N flowers will bloom one by one in N days. In each day, there will be exactly one flower blooming and it will be in the status of blooming since then.

Given an array flowers consists of number from 1 to N. Each number in the array represents the place where the flower will open in that day.

For example, flowers[i] = x means that the unique flower that blooms at day i will be at position x, where i and x will be in the range from 1 to N.

Also given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and these flowers are not blooming.

Improve this question
5
  • Format the question carefully please. Commented Feb 4, 2018 at 9:32
  • I have corrected some typo Commented Feb 4, 2018 at 10:15
  • We cannot access the Problem link, seems like it's only for premium users, can you update this post with the question as well. Thank you Commented Feb 4, 2018 at 13:18
  • I'm confused. You added a section to your question, "I will show you original problem here:" Is that a description of the problem you'd like help with or a description of the problem you already know how to solve? Commented Feb 4, 2018 at 22:30
  • Because some comments said they cannot open the link, because the link is for the prime number in leetcode. The reason why I attached the original one, is trying to make the description more clearly. I know how to solve the original question from leetcode, I am asking help for the variant which I posted at the beginning. I read you genius solution, however, I found some case is not correct, I have already listed the error case below. Could you help me fix that, I will appreciate your time and effort? Commented Feb 5, 2018 at 10:45

1 Answer 1

Reset to default
0

Let's translate the day lines to an array representing which position was updated each day:

day1：1 0 0 0 0 0 0
array: [None,1] means on day 1, flower 1 bloomed

day2：1 0 1 0 0 0 0
array: [None,1,3] means on day 2, flower 3 bloomed

day3：1 1 1 0 0 0 0
array: [None,1,3,2] means on day 3 flower 2 bloomed

day4：1 1 1 0 1 0 0
array: [None,1,3,2,5]

day5：1 1 1 0 1 1 0
array: [None,1,3,2,5,6]

day6：1 1 1 0 1 1 1 
array: [None,1,3,2,5,6,7]

day7：1 1 1 1 1 1 1
array: [None,1,3,2,5,6,7,4]

Now let's iterate over this array with a sliding window:

[None,1,3,2,5,6,7,4]
k: 1 |-|  min,max 1
k: 2 |---|  min,max 1,3
k: 3 |-----| min,max 1,3 and count is 3 so days must be consecutive,
             record (1,3) and day 3
k: 3   |-----| min,max 2,5 not consecutive
k: 3     |-----| min,max 2,6 not consecutive
k: 3       |-----| min,max 5,7 and count is 3 so days must be consecutive
                   also 6 is greater than 3 and (5,7) does not
                   overlap with (1,3) so the last day is now
                   known to be 6
k: 3         |-----| min,max 4,7 not consecutive
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Yes, I got you, you are genius! Thank you very much. Based on your solution, I come up an optimization for finding min and max in the sliding window, I can use two deques to find min and max when window is sliding, then time complexity is o(n).
I found a BUG! day1：1 0 0 0 0 0 0 day2：1 0 1 0 0 0 0 day3：1 1 1 0 0 0 0 1st time find k consecutive bloomed flowers update: lastDayBloomKflowers = 3 day4：1 1 1 1 0 0 0 in your algorithm, it will find day 4 is last day when there is k=3 flowers bloomed, however, day 4 is not valid because, from position 1 to 4, there are 4 consecutive flowers, rather than 3, so final solution should be day3
@宗天博 3,2,4 is also consecutive. Please clarify more specifically in the question exactly what qualifies as a valid sequence.
@宗天博 perhaps compare not just the last day, but the last interval - so if the last interval was (1,3) you would not accept (2,4) as the "last day," but if you find (4,6) then you can update. Would that help?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.