Evolve Duplicate Detection for Sliding Windows and Read-Heavy Queries

Problem Statement

In stream monitoring and event processing, systems frequently need to verify whether duplicate values occur within a sliding window of size k. When such queries are read-heavy and issued repeatedly for varying values of k over a stable log, recalculating window invariants on every query becomes a bottleneck.

Design a class DuplicateWindowAnalyzer that inspects an integer array nums and optimizes for read-heavy duplicate queries.

A pair of indices (i, j) is considered a duplicate pair if i != j and nums[i] == nums[j]. The distance between them is defined as abs(i - j).

Implement the following methods:

• __init__(nums: list[int]): Preprocesses the array in O(n) time and at most O(n) auxiliary space.
• has_duplicate_within(k: int) -> bool: Returns True if there exists any duplicate pair (i, j) with distance at most k (abs(i - j) int: Returns the smallest distance between any two identical values in the array. If no duplicates exist, returns -1. Must run in O(1) time.

Interface

class DuplicateWindowAnalyzer:
    def __init__(self, nums: list[int]):
        pass

    def has_duplicate_within(self, k: int) -> bool:
        pass

    def min_gap(self) -> int:
        pass

Examples

Example 1

Input:
analyzer = DuplicateWindowAnalyzer([1, 2, 3, 1, 2, 3])
analyzer.min_gap() -> 3
analyzer.has_duplicate_within(2) -> False
analyzer.has_duplicate_within(3) -> True
analyzer.has_duplicate_within(5) -> True

Explanation:
The identical elements are at distances:
- Value 1: indices 0 and 3 (distance = 3)
- Value 2: indices 1 and 4 (distance = 3)
- Value 3: indices 2 and 5 (distance = 3)
The minimum distance between any duplicates is 3. Any query with k >= 3 returns True; otherwise False.

Example 2

Input:
analyzer = DuplicateWindowAnalyzer([10, 20, 30, 40])
analyzer.min_gap() -> -1
analyzer.has_duplicate_within(10) -> False

Explanation:
All elements are unique, so min_gap is -1 and has_duplicate_within returns False for any k.

Constraints

• 1 = 1
• has_duplicate_within and min_gap may be called up to 10^5 times.