Gallery Active Visitors
Medium · queue
A gallery has a door scanner that logs every badge scan. Scan k was made by the visitor with badge number visitors[k] at second times[k]. The scans are listed in the order they happened, so the times never go down, and several scans can share the same second. A visitor may scan many times.
After each scan, the staff want to know how many different visitors have scanned lately. For a scan at second t, "lately" means every scan, including this one, with a time t' that satisfies t - window < t' <= t. A scan made exactly window seconds before t is too old to count.
Return a list with one number for each scan, in the same order as the scans.
Examples
Example 1
Input: times = [1, 2, 3, 8, 9], visitors = [7, 7, 5, 7, 5], window = 3
Output: [1, 1, 2, 1, 2]
At second 3 the recent scans are from seconds 1, 2 and 3, made by visitors 7, 7 and 5: two different visitors. At second 8 only the scan at second 8 is recent. At second 9 the scans at seconds 8 and 9 give visitors 7 and 5.
Example 2
Input: times = [0, 5], visitors = [4, 4], window = 5
Output: [1, 1]
The scan at second 0 is exactly 5 seconds old at second 5, so it no longer counts, and visitor 4 is counted once either way.
Example 3
Input: times = [4, 4, 4], visitors = [1, 2, 1], window = 10
Output: [1, 2, 2]
Constraints
- 1 <= len(times) = len(visitors) <= 10^5
- 0 <= times[i] <= 10^9, and times[i] <= times[i + 1]
- 1 <= visitors[i] <= 10^9
- 1 <= window <= 10^9