Constraints

• 0 <= len(transactions) <= 100000
• Each transaction_date is a valid date string in YYYY-MM-DD format
• Transactions are considered part of the same group only if merchant, amount, and currency all match exactly
• A group must have a valid streak of at least 3 transactions to be considered recurring

Examples

Solution

def solution(transactions):
    from collections import defaultdict
    from datetime import datetime
    import calendar

    def parse_date(s):
        return datetime.strptime(s, '%Y-%m-%d').date()

    def is_last_day(d):
        return d.day == calendar.monthrange(d.year, d.month)[1]

    def is_monthly_step(a, b):
        next_year = a.year + (1 if a.month == 12 else 0)
        next_month = 1 if a.month == 12 else a.month + 1
        if (b.year, b.month) != (next_year, next_month):
            return False
        return a.day == b.day or (is_last_day(a) and is_last_day(b))

    def longest_streak(dates, kind):
        if not dates:
            return 0
        best = 1
        cur = 1
        for i in range(1, len(dates)):
            prev = dates[i - 1]
            curr = dates[i]
            if kind == 'DAILY':
                ok = (curr - prev).days == 1
            elif kind == 'WEEKLY':
                ok = (curr - prev).days == 7
            else:
                ok = is_monthly_step(prev, curr)

            if ok:
                cur += 1
            else:
                cur = 1
            if cur > best:
                best = cur
        return best

    groups = defaultdict(list)
    for date_str, merchant, amount, currency in transactions:
        groups[(merchant, amount, currency)].append(parse_date(date_str))

    order = ['DAILY', 'WEEKLY', 'MONTHLY']
    result = []

    for (merchant, amount, currency), dates in groups.items():
        dates.sort()
        best_kind = None
        best_len = 0

        for kind in order:
            streak = longest_streak(dates, kind)
            if streak >= 3 and streak > best_len:
                best_len = streak
                best_kind = kind

        if best_kind is not None:
            result.append((merchant, amount, currency, best_kind))

    result.sort(key=lambda x: (x[0], x[1], x[2]))
    return result

Time complexity: O(n log n). Space complexity: O(n).

Hints

1. First group transactions by merchant, amount, and currency. Then you only need to analyze dates within each group.
2. After sorting dates in a group, look for the longest consecutive streak for each frequency type by checking adjacent date gaps.