Problem Link:
Author: rajpate77725
DIFFICULTY:
MEDIUM
PREREQUISITES:
ARRAY ,SLIDING WINDOW
PROBLEM:
On the lush alien world of Pandora live the Na'vi beings who appear primitive but are highly evolved.Doctor Grace runs a project which allows humans to transform in Avatar. Jake a paralyzed former Marine becomes mobile again through one such Avatar. Jake has been given a mission to become friends with the Na'vi people by transforming into Avatar.
The project runs for N days where on each day Jake can transform into Avatar for a specific amount of time. Through her experience, Doctor Grace can predict the transformation time of Jake for maximum K days. After each prediction, the next prediction occurs after F days.
Find the maximum Avatar time in each prediction.
EXPLANATION:
Observations: - Checkup is happening after every F days. - Out of f days trasformation can be predicted for max k days.
Approach: - We can use sliding window approach such that window slides after every F days and first k days of every F days can be choosen for a search of max element.
- We used the deque to store the required index of max element after every iteration.
- Whenever the max element comes we pop_back the element less than that element from the deque such that only the maximum element left at the back of the deque.
- Corner case is there for the elements after the every possible window size.
- After that we have the array of max element in every k interval.
- Then we print the element in the interval of f elements.
TIME COMPLEXITY:
O(N) per test case.