FastPrep
Problem · Binary Search

Min Days to Bloom

Learn this problem
● MediumGoogleOA
See Google hiring insights

Problem statement

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.

Function

minDays(roses: int[], k: int, n: int) → int

Examples

Example 1

roses = [1, 2, 4, 9, 3, 4, 1]k = 2n = 2return = 4
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.

Constraints

  • 1 ≤ roses.length ≤ 2 * 10^5
  • 1 ≤ roses[i] ≤ 10^9
  • 1 ≤ k, n ≤ roses.length
  • Each rose can belong to at most one bouquet. Return -1 when fewer than k * n roses are available.

More Google problems

drafts saved locally
public int minDays(int[] roses, int k, int n) {
    // write your code here
}
roses[1, 2, 4, 9, 3, 4, 1]
k2
n2
expected4
checking account