Suspicious Transaction Detector

Problem Context

You are building a fraud detection system for a fintech company. Given a list of timestamped transactions, your task is to identify all users who have made more than N transactions within any rolling window of M minutes.

This is a classic real-world problem that combines sliding window techniques with hash maps to efficiently track activity per user over time.

Input Format

• transactions: A list of tuples [userId, timestamp] where userId is a string and timestamp is an integer representing seconds since epoch. The list is sorted by timestamp in ascending order.
• n: An integer — the maximum allowed number of transactions in any M-minute window (inclusive threshold).
• m: An integer — the window duration in minutes.

Output Format

Return a sorted list of userIds (alphabetically) who have made more than N transactions in any rolling M-minute window.

Examples

Example 1

Input: transactions = [["alice", 0], ["alice", 30], ["alice", 60], ["bob", 0], ["alice", 90]], n = 2, m = 2
Output: ["alice"]
Explanation: M = 2 minutes = 120 seconds. Alice has transactions at t=0, 30, 60, 90. The window [0, 120) contains 4 transactions for Alice, which exceeds N=2. Bob only has 1 transaction, so he is not flagged.

Example 2

Input: transactions = [["alice", 0], ["bob", 10], ["alice", 70], ["bob", 80], ["bob", 90]], n = 2, m = 1
Output: ["bob"]
Explanation: M = 1 minute = 60 seconds. Bob has transactions at t=10, 80, 90. The window [30, 90] contains t=80 and t=90 — only 2, not more than 2. But window [80, 140) contains t=80 and t=90 — exactly 2, which does NOT exceed N=2. Wait — actually window starting at t=10 has t=10, 80 is outside 60s. Window at t=80 covers [80, 140): t=80 and t=90 = 2 transactions. That equals N but does not exceed. Let me re-check: Bob at t=10, 80, 90. [80-60=20, 80]: t=80 only? No — sliding to t=90: window [30, 90] has t=80, 90 = 2. Not exceeding. However Bob has 3 transactions and checking all windows... window ending at t=90: [90-60, 90] = [30, 90] → t=80, t=90 = 2, not > 2. So neither is flagged — output: []

Example 3

Input: transactions = [["carol", 100], ["carol", 110], ["carol", 120], ["carol", 130]], n = 2, m = 1
Output: ["carol"]
Explanation: All 4 of Carol's transactions fall within 30 seconds, well within the 60-second window. She has 4 > 2 transactions in that window.

Approach Hints