Top K Frequent Transactions

Problem Context

You are building a real-time fraud detection system for a financial platform. As transaction amounts stream in, you need to efficiently track and report the top K most frequently occurring transaction values at any point in time.

Given a list of transaction amounts (simulating a stream processed so far) and an integer k, return the k most frequent transaction amounts in descending order of frequency. If two amounts have the same frequency, return them in ascending order of value.

Input Format

• transactions: a list of integers representing transaction amounts
• k: an integer representing the number of top frequent values to return

Output Format

Return a list of k integers — the top k most frequent transaction amounts, ordered by:

1. Frequency (descending)
2. Value (ascending) for ties

Examples

Example 1

Input: transactions = [100, 200, 100, 300, 200, 100], k = 2 Output: [100, 200] Explanation: 100 appears 3 times, 200 appears 2 times, 300 appears 1 time. The top 2 are [100, 200].

Example 2

Input: transactions = [50, 75, 50, 75, 100, 100], k = 2 Output: [50, 75] Explanation: 50, 75, and 100 each appear 2 times. Among ties, return in ascending order of value, so [50, 75] are the top 2.

Example 3

Input: transactions = [500], k = 1 Output: [500] Explanation: Only one transaction amount exists, and k = 1, so the answer is [500].

Approach Hints

• Step 1: Use a hash map to count the frequency of each transaction amount in O(n) time.
• Step 2: To efficiently find the top k elements, consider using a min-heap of size k — this gives O(n log k) time complexity, which is optimal for large streams.
• Alternative: You could use bucket sort based on frequency to achieve O(n) time if the range of frequencies is bounded.
• Key insight: A min-heap of size k lets you maintain the top-k candidates efficiently: push each (frequency, value) pair, and pop when the heap exceeds size k. Remember to handle the tie-breaking rule (ascending value) in your comparator.
• Space complexity should be O(n) for the frequency map and O(k) for the heap.