bablu_45's blog

By bablu_45, history, 15 months ago, In English

Given an array of roses. roses[i] means rose i will bloom on day roses[i]. Also given an int k, which is the minimum number of adjacent bloom roses required for a bouquet, and an int n, which is the number of bouquets we need. Return the earliest day that we can get n bouquets of roses.

Example: Input: roses = [1, 2, 4, 9, 3, 4, 1], k = 2, n = 2

Output: 4

Explanation:

day 1: [b, n, n, n, n, n, b]. The first and the last rose bloom.

day 2: [b, b, n, n, n, n, b]. The second rose blooms. Here the first two bloom roses make a bouquet.

day 3: [b, b, n, n, b, n, b]

day 4: [b, b, b, n, b, b, b]

Here the last three bloom roses make a bouquet, meeting the required n = 2 bouquets of bloom roses. So return day 4.

I am looking for a efficient D.P solution (if possible).

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
15 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Do a binary search on number of days. the complexity would be O(log(num_days)) * O(num_roses)

  • »
    »
    15 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I am sorry that I forgot to mention that I was looking for an efficient D.P solution (if possible) even if it's worse than binary search.

    Thanks anyway.

»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

$$$O(n)$$$ solution:

Wlog suppose the array has length which is a multiple of $$$k$$$. Decompose the array into blocks of length $$$k$$$, and in each block, compute prefix maximums and suffix maximums. Now, for any window of length $$$k$$$, we can query the maximum in that window in $$$O(1)$$$ time by combining a suffix and prefix of two adjacent blocks. So, iterate over all windows of length $$$k$$$, and find the window with smallest maximum. That's the answer.

This is a common technique known as sliding window RMQ or fixed-range RMQ.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    That would be correct if you wanted to make only one bouquet, but I think you need to make n bouqets...

    Correct me if I am wrong.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Oh, you're completely right, I didn't read the problem correctly.

      Of course the binary search solution still works in $$$O(m\log(\max(\text{roses})))$$$. (Let $$$m$$$ be the length of the original array). We can use compression to get $$$O(m\log m)$$$ as well. I don't think it can be solved any faster than that for $$$n\neq 1$$$.