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.