Detect Duplicated Charges

MediumPython

Problem

Credit Genie receives a chronological stream of card charge events. A charge is potentially duplicated when the same account is charged the same merchant for the same amount and currency within a specified time window.

Implement detect_duplicate_charges, returning one pair for each duplicate event. For a duplicate at index i, pair it with the most recent earlier active event having the same charge signature.

Formal Specification

Input transactions is a list of dictionaries with keys timestamp, account_id, merchant_id, amount_cents, and currency. Timestamps are integer seconds and are nondecreasing. window_seconds is a nonnegative integer. Return a list of [previous_index, duplicate_index] pairs in stream order.

An earlier transaction remains active when previous_timestamp >= current_timestamp - window_seconds. Transactions outside the window cannot be paired. The current transaction is checked before it is added to the active window, so it cannot match itself.

Constraints

1 <= len(transactions) <= 200000
0 <= timestamp <= 10^12
0 <= amount_cents <= 10^9
Each required string has at most 100 characters
Timestamps are nondecreasing
The time window includes events exactly window_seconds seconds before the current event

Function Signature

def detect_duplicate_charges(transactions, window_seconds):

Implement detect_duplicate_charges, returning one pair for each duplicate event. For a duplicate at index i, pair it with the most recent earlier active event having the same charge signature.