Detect recurring transactions from a ledger

You are given a list of credit/debit card transactions. Each transaction has:

• transaction_date (YYYY-MM-DD)
• merchant (string)
• amount (decimal, positive)
• currency (string, e.g., USD )

Many transactions are one-off (e.g., small public transit fares), while some are recurring subscriptions/bills (e.g., Netflix).

Task

Identify recurring transactions and print a summary line per detected recurring pattern, in the form:

• merchant, <amount> per <period>

Example output:

• Netflix, $30 per month
• GymCo, $12.99 per week

Requirements / Clarifications

1. Recurring transactions should be detected even if there are many non-recurring transactions from the same merchant (e.g., repeated but irregular small charges).
2. Your solution should support multiple recurrence periods, at least:
   • daily
   • weekly
   • monthly (bonus: yearly)
3. Assume transactions for different currencies should not be mixed (i.e., treat (merchant, currency) as separate streams unless you explicitly design conversion).
4. Define and justify what “recurring” means (e.g., minimum number of occurrences, acceptable date jitter for monthly billing, and whether amount must match exactly or within a tolerance).

Input/Output

• Input: an array/list of transactions in arbitrary order.
• Output: a list of recurring summaries. If multiple recurring patterns exist for the same merchant (e.g., two different subscription tiers), include each separately.

Constraints (assume)

• Up to 100,000 transactions.
• Dates span up to several years.

Example

Input (abridged):

• 2024-01-05, Netflix, 30.00, USD
• 2024-02-05, Netflix, 30.00, USD
• 2024-03-05, Netflix, 30.00, USD
• 2024-01-02, CityTransit, 2.75, USD
• 2024-01-09, CityTransit, 2.75, USD
• 2024-01-13, CityTransit, 2.75, USD (may or may not be considered “recurring” depending on your definition)

Expected output includes something like:

• Netflix, $30.00 per month

Explain your approach and the time/space complexity.