# Rose Garden Google OA 2023 Solution

## Rose Garden Google OA 2023 Solution

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.

### SOLUTION

Program: Rose Garden Google OA Solution in Python

``````import collections
def minDaysBloom(roses, k, n):
days = collections.defaultdict(set)
for i, d in enumerate(roses):
startings = {}
endings = {}
count = 0
def boutiques(interval):
return (interval[1] - interval[0] + 1 // k)

for d in sorted(list(days.keys())):
for i in days[d]:
if i-1 in endings and i+1 in startings:
i1, i2 = endings[i-1], startings[i+1]
new_i = [i1[0], i2[1]]
del endings[i1[1]]
del endings[i2[1]]
del startings[i1[0]]
del startings[i2[0]]
endings[new_i[1]] = new_i
startings[new_i[1]] = new_i

count += boutiques(new_i) - boutiques(i1) - boutiques(i2)
continue

if i-1 in endings:
interval = endings[i-1]
count -= boutiques(interval)
interval[1] += 1
count += boutiques(interval)
del endings[i-1]
endings[i] = interval
continue

if i+1 in startings:
interval = startings[i+1]
count -= boutiques(interval)
interval[0] -= 1
count += boutiques(interval)
del startings[i+1]
startings[i] = interval
continue

new_i = [i, i]
endings[i] = new_i
startings[i] = new_i
count += boutiques(new_i)

print(d, count, endings, startings)
if count >= n:
return d

return -1

print(minDaysBloom([1, 2, 4, 9, 3, 4, 1],2,2))  # should print 4``````

Program: Rose Garden Google OA Solution in C++

``````#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <algorithm>

using namespace std;

int getEarliestDay(const vector<int>& roses, int k, int n) {
vector<int> bloomStatus(roses.size(), 0);
std::unordered_map<int,vector<int>> dayToPosMap;
for (int i=0; i<roses.size(); i++)  dayToPosMap[roses[i]].push_back(i);

int maxDay = *std::max_element(roses.begin(), roses.end());

for (int i=1; i<=maxDay; ++i) {
if (dayToPosMap.find(i) == dayToPosMap.end())  continue;

for (int j=0; j<dayToPosMap[i].size(); ++j)    bloomStatus[dayToPosMap[i][j]] = 1;

int countBouquets = 0;
for (int j=0; j<bloomStatus.size(); ++j) {
if (bloomStatus[j] == 0) continue;
int numContinuousRoses = 0;
while ((j<bloomStatus.size()) && (bloomStatus[j]==1)) {
++numContinuousRoses;
if (numContinuousRoses == k) {
++countBouquets;
std::cout << "Day " << i << "\tNumber of Bouquets = " << countBouquets << "\n";
if (countBouquets == n)    return i; //Earliest Day = i
numContinuousRoses = 0;
}
++j;
}
}
}

return maxDay;
}

int main() {
vector<int> roses = {1, 2, 4, 9, 3, 4, 1};
int earliestDay = getEarliestDay(roses, 2, 2);
std::cout << "\nEarliest Day: " << earliestDay << "\n";

return 0;
}``````

Program: Rose Garden Google OA Solution in Java

1. if K * N > roses.Length, no result
2. if can find Ns K adjacent roses before reach to the end of the array. For example minDaysBloom(roses, 2, 2), just return max roses[i], maintain one variable is enough
3. for minDaysBloom(roses, 3, 2), will scan to the end of the array, and because we know if reached to the end, there will be a result anyway as K * N <= roses.Length, so need cache all maximum days for each roses[i, …i + K], then sort this list, and return Nth element from this list.
`````` public static int minDaysBloom(int[] roses, int k, int n)
{
if (k * n > roses.Length) return -1;

int bouquets = 0;
int days = int.MinValue;
var daysSet = new HashSet<int>();
int i = 0;
while (i < roses.Length)
{
var day = int.MinValue;
for (int j = i; j < i + k && j < roses.Length; j++)
{
day = Math.Max(day, roses[j]);
if (j < i + k - 1)
{
adjacent = Math.Abs(roses[j] - roses[j + 1]) == 1;
}
}

{
bouquets++;
days = Math.Max(days, day);
if (bouquets >= n) return days;
i += k;
}
else
{