NINJAS GARDEN

The idea here is to go to every position and check for the given condition. If at any position our condition becomes true we return that day as the answer.

Algorithm:

• Initialize an array ‘dayOfFlowerBloomed’ to store days on which each flower will bloom.
• Traverse the days array with i starting from zero and update the array as dayOfFlowerBloomed[flower[i]] = i + 1.
• Set result as INT_MAX
• Traverse the array again. Store the left and right values with k slots between 2 variables and find it maximum.
• At each step traverse from 1 to K and check if dayOfFlowerBloomed[i + j] is less than the maximum value, break the inner loop, and set done false.
• If the done is true, set the ans as the maximum value.
• If the ans is equal to INT_MAX return -1 else return ans.

The idea here is to find the window of size K + 2 such that in window endpoints refer to a position where the flower has bloomed and all other points in the window refer to points where the flower has not bloomed. So we will use the concept of binary index tree here as suppose binaryindex[i] represents the numbers of flower bloomed from day 1 to day N then if binaryindex[i] - binaryindex[i - k - 2] == 2 and day[i] and day[i - k - 1] have flower bloomed then we can say that in window [i - k - 1, i] only day[i] and day[i - k - 1] have flowers bloomed.

So we need to process two types of queries

1. Make flower bloomed at day i i.e. add 1 to index 'i' in Fenwick Tree

2. For each 'i' check if it can be an endpoint of the window.

i.e. Check if window [i - k - 1,i] or [i, i + k + 1] is valid. So we need to do the above two queries fast. So we will use the Binary Index tree to process these two types of queries.

Algorithm:

• Firstly we declare a bool array named as ‘done’ for storing that how many flowers have already bloomed. ‘done[i] == true’ represents that ‘ith’ flower has already been bloomed and vice versa.
• Now we have created a class name as Fenwick tree which has two functions ‘add’ and ‘sum’ add function to add the value at index in the array of Fenwick tree and ‘sum’ function gives us the sum of all elements of Fenwick tree from ‘1’ to ‘N’.
• Now we create the object of the Fenwick tree class ‘bit’ and start iterating the given array to check whether it is a valid start or endpoint of the window.
• Now for every value of a given array, we check in the ‘done’ array :
  • If the flower is bloomed for that value we add the index in the Fenwick tree
  • Else we iterate further
• Now we checked whether the value is starting or the endpoint of the window by calling the sum method to get the sum up to window size:
  • If the difference between them is equal to ‘2’ we return that index +  1 as our answer
  • Else we iterate further
• After the loop, we simply return ‘-1’ that represents no such window found.

The idea here is to build another array of days where ‘dayOfFlowerBloomed[i]’ represents which day (1-based) a flower at position i + 1 bloom. Now, we can initialize a window [0, K + 1] and try looking for the right window. When we are iterating the days, we look if dayOfFlowerBloomed[i] is greater than ‘dayOfFlowerBloomed[let]’ and ‘dayOfFlowerBloomed[right]’, we can continue our traversal. Else, if dayOfFlowerBloomed[i] < dayOfFlowerBloomed[left] or dayOfFlowerBloomed[i] < dayOfFlowerBloomed[right], becomes true we can say that we have found a  flower in between our window that blooms earlier than the left and right flower so it cannot be in the window. So we shift the window and iterate further. If there is a window in which ‘dayOfFlowerBloomed[i]’ is always greater than ‘dayOfFlowerBloomed[left]’ and ‘dayOfFlowerBloomed[right]’, we found a solution

Suppose the array is [ 1, 2, 3, 4 ], k = 1 so we initialize 3 variable ‘left’, ‘right’ and ‘i = left + 1’ and right is initialized from ‘K + 1’ now we start increasing the value of i and compare it with left and right till i is less than right.

Algorithm:

• Firstly we initialize a window [0, K + 1] and start iterating the days.
• While we are iterating the days, as long as dayOfFlowerBloomed[i] is greater than ‘dayOfFlowerBloomed[left]’ and ‘dayOfFlowerBloomed[right]’, we continue iterating.
• If dayOfFlowerBloomed[i] < dayOfFlowerBloomed[left] or dayOfFlowerBloomed[i] < dayOfFlowerBloomed[right], we found a middle flower that blooms earlier.
• If it is not present in the window, we shift the window such that left = i and right = left + K + 1.
• If all days between left and right are later, we return the answer.