Skip to content

1482. Minimum Number of Days to Make m Bouquets 👍

  • Time: $O(n\log (\max(\texttt{bloomDay})))$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
 public:
  int minDays(vector<int>& bloomDay, int m, int k) {
    if (bloomDay.size() < static_cast<long>(m) * k)
      return -1;

    int l = ranges::min(bloomDay);
    int r = ranges::max(bloomDay);

    while (l < r) {
      const int mid = (l + r) / 2;
      if (getBouquetCount(bloomDay, k, mid) >= m)
        r = mid;
      else
        l = mid + 1;
    }

    return l;
  }

 private:
  // Returns the number of bouquets (k flowers needed) can be made after the
  // `waitingDays`..
  int getBouquetCount(const vector<int>& bloomDay, int k, int waitingDays) {
    int bouquetCount = 0;
    int requiredFlowers = k;
    for (const int day : bloomDay)
      if (day > waitingDays) {
        // Reset `requiredFlowers` since there was not enough adjacent flowers.
        requiredFlowers = k;
      } else if (--requiredFlowers == 0) {
        // Use k adjacent flowers to make a bouquet.
        ++bouquetCount;
        requiredFlowers = k;
      }
    return bouquetCount;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
  public int minDays(int[] bloomDay, int m, int k) {
    if (bloomDay.length < (long) m * k)
      return -1;

    int l = Arrays.stream(bloomDay).min().getAsInt();
    int r = Arrays.stream(bloomDay).max().getAsInt();

    while (l < r) {
      final int mid = (l + r) / 2;
      if (getBouquetCount(bloomDay, k, mid) >= m)
        r = mid;
      else
        l = mid + 1;
    }

    return l;
  }

  // Returns the number of bouquets (k flowers needed) can be made after the
  // `waitingDays`..
  private int getBouquetCount(int[] bloomDay, int k, int waitingDays) {
    int bouquetCount = 0;
    int requiredFlowers = k;
    for (final int day : bloomDay)
      if (day > waitingDays) {
        // Reset `requiredFlowers` since there was not enough adjacent flowers.
        requiredFlowers = k;
      } else if (--requiredFlowers == 0) {
        // Use k adjacent flowers to make a bouquet.
        ++bouquetCount;
        requiredFlowers = k;
      }
    return bouquetCount;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
  def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
    if len(bloomDay) < m * k:
      return -1

    def getBouquetCount(waitingDays: int) -> int:
      """
      Returns the number of bouquets (k flowers needed) can be made after the
      `waitingDays`.
      """
      bouquetCount = 0
      requiredFlowers = k
      for day in bloomDay:
        if day > waitingDays:
          # Reset `requiredFlowers` since there was not enough adjacent flowers.
          requiredFlowers = k
        else:
          requiredFlowers -= 1
          if requiredFlowers == 0:
            # Use k adjacent flowers to make a bouquet.
            bouquetCount += 1
            requiredFlowers = k
      return bouquetCount

    l = min(bloomDay)
    r = max(bloomDay)

    while l < r:
      mid = (l + r) // 2
      if getBouquetCount(mid) >= m:
        r = mid
      else:
        l = mid + 1

    return l