Problem statement

https://binarysearch.com/problems/Window-Queries/

Solution

The idea is for each value find all places where we meet it (also add -1 and n to ends). Then let us calculate number of windows of length w, which do not have value. If we have value on places a and b, then we have max(b - a - w, 0) such windows. Then we sum them over all gaps.

Complexity

It is O(n + q) for time and space

Code

class Solution:
    def solve(self, A, Q, w):
        places, n = defaultdict(list), len(A)
        for i, x in enumerate(A):
            places[x] += [i]

        d = {}
        for x in places:
            arr = [-1] + places[x] + [n]
            d[x] = n - w + 1 - sum(max(b - a - w, 0) for a, b in zip(arr, arr[1:]))

        return [d[q] for q in Q]