Category Spending Tracker
Intuit's financial products help millions manage their money. A core feature for many users is understanding where their money goes. One common requirement is to identify top spending categories over time. This problem challenges you to design a system that dynamically tracks spending across categories, allowing transactions to be added, updated, or voided, and efficiently provides the top K spending categories at any given moment.
You are tasked with implementing a CategorySpendingTracker class that supports the following operations:
constructor(k: number): Initializes the tracker with a specified k, representing the maximum number of top spending categories to retrieve.recordTransaction(transactionId: string, category: string, amount: number): Records a financial transaction. If transactionId already exists, it implies an update to an existing transaction (its category or amount might change). If it's a new transactionId, it's added.voidTransaction(transactionId: string): Removes a previously recorded transaction identified by transactionId. If the transactionId does not exist, this operation should do nothing.getTopKCategories(): string[]: Returns a list of strings, representing the k categories with the highest total spending. The categories should be ordered by their total spending in descending order. If fewer than k categories have positive spending, return all such categories.Class: CategorySpendingTracker
constructor(k: number)
k: An integer representing the maximum number of top categories to return.recordTransaction(transactionId: string, category: string, amount: number)
transactionId: A unique string identifier for the transaction.category: A string representing the spending category (e.g., "Groceries", "Rent").amount: A number representing the transaction amount. Always positive.voidvoidTransaction(transactionId: string)
transactionId: The unique string identifier of the transaction to be removed.voidgetTopKCategories(): string[]
amount values will be positive integers.transactionId values are unique string identifiers.getTopKCategories() is called and there are no recorded transactions with positive spending, an empty array should be returned.getTopKCategories() result.Examples
Example 1
Input:
operations = ["CategorySpendingTracker","recordTransaction","recordTransaction","recordTransaction","getTopKCategories","recordTransaction","getTopKCategories"], params = [[2],["t1","Groceries",100],["t2","Rent",1000],["t3","Utilities",50],[],["t4","Groceries",200],[]]
Output:
[null,null,null,null,["Rent","Groceries"],null,["Rent","Groceries"]]
Note:
Example 2
Input:
operations = ["CategorySpendingTracker","recordTransaction","recordTransaction","recordTransaction","getTopKCategories","voidTransaction","getTopKCategories"], params = [[1],["txA","Food",500],["txB","Transport",200],["txC","Food",100],[],["txA"],[]]
Output:
[null,null,null,null,["Food"],null,["Transport"]]
Note:
Example 3
Input:
operations = ["CategorySpendingTracker","recordTransaction","recordTransaction","getTopKCategories","recordTransaction","getTopKCategories"], params = [[2],["id1","Books",50],["id2","Food",150],[],["id1","Books",200],[]]
Output:
[null,null,null,["Food","Books"],null,["Books","Food"]]
Note:
Constraints
1 <= k <= 10001 <= transactionId.length, category.length <= 501 <= amount <= 10^9recordTransaction calls will not exceed 10^5.voidTransaction calls will not exceed 10^5.getTopKCategories calls will not exceed 10^4.number is sufficient).K categories?O(log N) or O(K log N) for queries/updates).K elements.Loading editor...