All problems

Favourite in the Window

Hard · sliding window

A bakery writes down every order as an item id, in the order the orders arrive. The list is orders. You are also given a number k.

Look at every group of k orders in a row, starting with the first k orders and sliding one order at a time until the group ends at the last order. In each group, the favourite is the item ordered the most times. If several items share the highest count, the favourite is the one with the smallest id.

Return a list with the favourite of every group, from the first group to the last. It has len(orders) - k + 1 values.

Examples

Example 1

Input: orders = [3, 1, 3, 2, 2], k = 3

Output: [3, 1, 2]

The groups are [3, 1, 3], [1, 3, 2] and [3, 2, 2]. In the middle group every item appears once, so the smallest id, 1, wins.

Example 2

Input: orders = [5, 5, 7, 7], k = 2

Output: [5, 5, 7]

The groups are [5, 5], [5, 7] and [7, 7]. The middle group is a tie, so 5 wins.

Example 3

Input: orders = [9], k = 1

Output: [9]

Constraints