Maximum Freshness in Harvest Windows

Moderate

0/80

0 upvote

Asked in company

Problem statement

You have a row of fruit baskets represented by an array freshness, where each element is the freshness score of the fruit in that basket. You are also given a basket cart size k.

You will slide this cart of size k along the row of baskets, one basket at a time, from left to right. For each position of the cart (each "window" of k baskets), you need to determine the maximum freshness score within that window.

Your task is to return a list of the maximum freshness scores for each k-sized window.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains two space-separated integers, 'N' and 'K'.

The second line contains 'N' space-separated integers, representing the freshness array.

Output Format:

Print a single line containing N-K+1 space-separated integers, where each integer is the maximum value for each consecutive window of size K.

Note:

A naive solution of iterating through each of the N-K+1 windows and finding the maximum in each would be O(N * K), which is too slow for the given constraints.

The optimal solution uses a sliding window approach with a Deque (Double-Ended Queue). The deque is used to store indices of elements in the current window, maintained in decreasing order of their freshness scores. This allows finding the maximum for each window in O(1) amortized time, leading to an overall O(N) solution.

Sample Input 1:

8 3
1 3 -1 -3 5 3 6 7

Sample Output 1:

3 3 5 5 6 7

Explanation for Sample 1:

- Window 1: `[1, 3, -1]`, max is 3.
- Window 2: `[3, -1, -3]`, max is 3.
- Window 3: `[-1, -3, 5]`, max is 5.
- Window 4: `[-3, 5, 3]`, max is 5.
- Window 5: `[5, 3, 6]`, max is 6.
- Window 6: `[3, 6, 7]`, max is 7.

Sample Input 2:

5 1
10 20 30 40 50

Sample Output 2:

10 20 30 40 50

Explanation for Sample 2:

When the window size is 1, the maximum of each window is simply the element itself.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

1 <= K <= N <= 10^5
-10^9 <= freshness[i] <= 10^9

Time limit: 1 sec

Approaches (1)

Approach 1

Sliding Window

Time Complexity

Space Complexity

(100% EXP penalty)

Maximum Freshness in Harvest Windows

Console