Detect k events in a sliding window

Implement an algorithm that, for each user, determines whether there exists a set of at least k ACH credit events from distinct device_ids within any sliding window of t minutes where each amount_cents ≥ X. If so, output the earliest such window [start_ts, end_ts] and the k device_ids; otherwise output none. Input - events: iterable of (user_id INT, device_id TEXT, ts ISO-8601 string, amount_cents INT), up to n=1e6 total events across users, potentially out of order by ≤5 minutes. Parameters - k ∈ {3,4,5}; t up to 1440; X ≥ 0. Requirements - Time: O(n log n) overall; Space: O(m) where m is max events per user within t-minute horizon. - Handle out-of-order events (≤5 minutes skew) and deduplicate exact duplicates. - Timestamps are UTC; beware DST transitions and clock skew. - Return all qualifying users with their earliest window and devices. Follow-ups 1) Describe a streaming approach (bounded memory) if events arrive per user partition. 2) Prove correctness of your window advancement and distinct-device counting. 3) Discuss worst-case behavior on highly bursty users and how to mitigate.