Max Avatar Time

Revision en2, by viraj.jadhav20, 2023-02-04 13:16:45

Author: rajpate77725

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.

## CODE:

Editorialist's Code(C++)

#### History

Revisions

Rev. Lang. By When Δ Comment
en2 viraj.jadhav20 2023-02-04 13:16:45 30 Tiny change: 'Author**: [Raj Pate]<br/>\n\n*' -> 'Author**: @rajpate7774<br/>\n\n*'
en1 viraj.jadhav20 2023-02-04 13:12:01 3417 Initial revision (published)