"""
PROBLEM: Fraudulent Transaction Detection

Stripe processes billions of transactions daily. To protect merchants, we need to 
identify potentially fraudulent transactions based on user behavior patterns.

A transaction is considered SUSPICIOUS if ANY of the following conditions are met:
1. The user makes more than 3 transactions within any 60-second window
2. The user's transactions in any 60-second window exceed $3000 total
3. The user makes a transaction from a different city within 30 minutes of a previous 
   transaction (impossible travel)

You are given a list of transactions, where each transaction is formatted as:
    "timestamp,user_id,amount,city"
    
- timestamp: Unix timestamp (integer, seconds)
- user_id: String identifier for the user
- amount: Transaction amount in dollars (float)
- city: City where transaction occurred (string)

Return a list of transaction indices (0-indexed) that are SUSPICIOUS, sorted in 
ascending order.

EXAMPLES:

Input: [
    "1609459200,user1,100.00,NYC",      # 0: OK
    "1609459210,user1,200.00,NYC",      # 1: OK
    "1609459220,user1,300.00,NYC",      # 2: OK
    "1609459230,user1,400.00,NYC",      # 3: SUSPICIOUS (4th transaction in 60s)
    "1609459300,user2,3500.00,LA",      # 4: SUSPICIOUS (exceeds $3000)
    "1609462000,user1,50.00,Chicago",   # 5: OK (2800 seconds / ~46 min later)
]
Output: [3, 4]

Input: [
    "1609459200,user1,100.00,NYC",      # 0: OK
    "1609459500,user1,200.00,LA",       # 1: SUSPICIOUS (different city within 30 min)
]
Output: [1]

CONSTRAINTS:
- 1 <= len(transactions) <= 100,000
- All timestamps are valid Unix timestamps
- 0 < amount <= 100,000
- user_id contains only alphanumeric characters
- city contains only alphabetic characters

"""

from collections import defaultdict
from typing import List


def find_suspicious_transactions(transactions: List[str]) -> List[int]:
    """
    Identify suspicious transactions based on fraud detection rules.
    
    Time Complexity: O(n * m) where n = number of transactions, 
                     m = max transactions per user in a 60-second window
    Space Complexity: O(n) for storing parsed transactions
    """
    
    # Parse all transactions
    parsed = []
    for i, txn in enumerate(transactions):
        parts = txn.split(',')
        timestamp = int(parts[0])
        user_id = parts[1]
        amount = float(parts[2])
        city = parts[3]
        parsed.append({
            'index': i,
            'timestamp': timestamp,
            'user_id': user_id,
            'amount': amount,
            'city': city
        })
    
    # Group transactions by user for efficient processing
    user_transactions = defaultdict(list)
    for txn in parsed:
        user_transactions[txn['user_id']].append(txn)
    
    # Sort each user's transactions by timestamp
    for user_id in user_transactions:
        user_transactions[user_id].sort(key=lambda x: x['timestamp'])
    
    suspicious = set()
    
    for user_id, txns in user_transactions.items():
        for i, current_txn in enumerate(txns):
            current_time = current_txn['timestamp']
            
            # Check rules within 60-second window (Rules 1 & 2)
            window_start = current_time - 60
            window_txns = []
            window_amount = 0
            
            for j in range(i, -1, -1):  # Look backwards from current
                if txns[j]['timestamp'] >= window_start:
                    window_txns.append(txns[j])
                    window_amount += txns[j]['amount']
                else:
                    break
            
            # Rule 1: More than 3 transactions in 60-second window
            if len(window_txns) > 3:
                suspicious.add(current_txn['index'])
            
            # Rule 2: Total amount exceeds $3000 in 60-second window
            if window_amount > 3000:
                suspicious.add(current_txn['index'])
            
            # Rule 3: Different city within 30 minutes (impossible travel)
            if i > 0:
                thirty_min_ago = current_time - 1800  # 30 * 60 = 1800 seconds
                
                for j in range(i - 1, -1, -1):
                    prev_txn = txns[j]
                    if prev_txn['timestamp'] >= thirty_min_ago:
                        if prev_txn['city'] != current_txn['city']:
                            suspicious.add(current_txn['index'])
                            break
                    else:
                        break
    
    return sorted(list(suspicious))


# ============================================================================
# TEST CASES
# ============================================================================

def test_find_suspicious_transactions():
    # Test Case 1: More than 3 transactions in 60 seconds
    transactions1 = [
        "1609459200,user1,100.00,NYC",
        "1609459210,user1,200.00,NYC",
        "1609459220,user1,300.00,NYC",
        "1609459230,user1,400.00,NYC",  # 4th transaction - suspicious
        "1609459300,user2,100.00,LA",
    ]
    result1 = find_suspicious_transactions(transactions1)
    assert result1 == [3], f"Test 1 failed: expected [3], got {result1}"
    print("✓ Test 1 passed: Detects >3 transactions in 60s window")
    
    # Test Case 2: Amount exceeds $3000 in 60-second window
    transactions2 = [
        "1609459200,user1,1000.00,NYC",
        "1609459210,user1,1500.00,NYC",
        "1609459220,user1,600.00,NYC",  # Total now $3100 - suspicious
    ]
    result2 = find_suspicious_transactions(transactions2)
    assert result2 == [2], f"Test 2 failed: expected [2], got {result2}"
    print("✓ Test 2 passed: Detects amount >$3000 in 60s window")
    
    # Test Case 3: Impossible travel (different city within 30 min)
    transactions3 = [
        "1609459200,user1,100.00,NYC",
        "1609459500,user1,200.00,LA",  # Different city, only 5 min later
    ]
    result3 = find_suspicious_transactions(transactions3)
    assert result3 == [1], f"Test 3 failed: expected [1], got {result3}"
    print("✓ Test 3 passed: Detects impossible travel")
    
    # Test Case 4: Same city within 30 min is OK
    transactions4 = [
        "1609459200,user1,100.00,NYC",
        "1609459500,user1,200.00,NYC",  # Same city - OK
    ]
    result4 = find_suspicious_transactions(transactions4)
    assert result4 == [], f"Test 4 failed: expected [], got {result4}"
    print("✓ Test 4 passed: Same city transactions are not flagged")
    
    # Test Case 5: Multiple users don't affect each other
    transactions5 = [
        "1609459200,user1,100.00,NYC",
        "1609459210,user2,200.00,LA",
        "1609459220,user1,300.00,NYC",
        "1609459230,user2,400.00,LA",
    ]
    result5 = find_suspicious_transactions(transactions5)
    assert result5 == [], f"Test 5 failed: expected [], got {result5}"
    print("✓ Test 5 passed: Different users are independent")
    
    # Test Case 6: Multiple rules violated
    transactions6 = [
        "1609459200,user1,2000.00,NYC",
        "1609459210,user1,500.00,NYC",
        "1609459220,user1,300.00,NYC",
        "1609459230,user1,400.00,LA",  # >3 txns, >$3000, different city
    ]
    result6 = find_suspicious_transactions(transactions6)
    assert result6 == [3], f"Test 6 failed: expected [3], got {result6}"
    print("✓ Test 6 passed: Multiple violations on same transaction")
    
    # Test Case 7: Window resets after 60 seconds
    transactions7 = [
        "1609459200,user1,100.00,NYC",
        "1609459210,user1,200.00,NYC",
        "1609459220,user1,300.00,NYC",
        "1609459400,user1,400.00,NYC",  # 200 seconds later - new window
        "1609459410,user1,500.00,NYC",
        "1609459420,user1,600.00,NYC",
    ]
    result7 = find_suspicious_transactions(transactions7)
    assert result7 == [], f"Test 7 failed: expected [], got {result7}"
    print("✓ Test 7 passed: 60-second window resets properly")
    
    # Test Case 8: Large single transaction
    transactions8 = [
        "1609459200,user1,3500.00,NYC",  # Single transaction >$3000
    ]
    result8 = find_suspicious_transactions(transactions8)
    assert result8 == [0], f"Test 8 failed: expected [0], got {result8}"
    print("✓ Test 8 passed: Single large transaction flagged")
    
    # Test Case 9: Edge case - exactly 3 transactions (should be OK)
    transactions9 = [
        "1609459200,user1,100.00,NYC",
        "1609459210,user1,200.00,NYC",
        "1609459220,user1,300.00,NYC",
    ]
    result9 = find_suspicious_transactions(transactions9)
    assert result9 == [], f"Test 9 failed: expected [], got {result9}"
    print("✓ Test 9 passed: Exactly 3 transactions is not suspicious")
    
    # Test Case 10: Edge case - exactly $3000 (should be OK)
    transactions10 = [
        "1609459200,user1,1000.00,NYC",
        "1609459210,user1,1000.00,NYC",
        "1609459220,user1,1000.00,NYC",
    ]
    result10 = find_suspicious_transactions(transactions10)
    assert result10 == [], f"Test 10 failed: expected [], got {result10}"
    print("✓ Test 10 passed: Exactly $3000 is not suspicious")
    
    print("\n" + "="*50)
    print("All tests passed! ✓")
    print("="*50)


if __name__ == "__main__":
    test_find_suspicious_transactions()
    
    # Example from problem description
    print("\n--- Running Example from Problem Description ---\n")
    example = [
        "1609459200,user1,100.00,NYC",
        "1609459210,user1,200.00,NYC",
        "1609459220,user1,300.00,NYC",
        "1609459230,user1,400.00,NYC",
        "1609459300,user2,3500.00,LA",
        "1609462000,user1,50.00,Chicago",  # 46 min later, different city OK
    ]
    result = find_suspicious_transactions(example)
    print(f"Input transactions: {len(example)} transactions")
    print(f"Suspicious indices: {result}")
    print(f"Expected: [3, 4]")