performance-optimizer

Score Breakdown

Your Submission

{
  "explanation": "BOTTLENECK IDENTIFICATION:\n\nThe dominant bottleneck was the `isAboveThreshold()` function, which was called once per transaction inside the inner loop. Each call performed: (1) a full O(n) filter of ALL transactions to find same-category items, (2) an O(m log m) sort to compute the median. For a dataset with n transactions across k categories with ~m transactions each, this produced O(n * m * (n + m log m)) ≈ O(n² log n) total complexity — quadratic in the number of transactions.\n\nSECONDARY BOTTLENECKS:\n1. `categories.includes()` in the deduplication loop — O(n*k) due to linear scan of the categories array on each transaction. Replaced with a Map/Set-based approach for O(1) lookups.\n2. `transactions.filter()` per category — another O(n) per category pass. Eliminated by pre-grouping into a Map.\n3. String concatenation with `+=` — creates O(n) intermediate string copies, leading to O(n²) total character copying. Replaced with array push + join pattern for O(n) total.\n\nALGORITHMIC IMPROVEMENTS:\n- Pre-group transactions by category using a Map: O(n) single pass instead of O(n*k) filter per category.\n- Precompute all category medians once upfront: O(n log n) total (one sort per category) instead of O(n² log n) (re-sorting for every transaction).\n- Compute the flag threshold `median * 1.97` once per category, not per transaction.\n- Use string array with join() instead of string concatenation to avoid quadratic string copying.\n\nCOMPLEXITY ANALYSIS:\n- Original: O(n² log n) due to repeated median computation\n- Optimized: O(n log n) dominated by the per-category sorts for median computation\n- Space: O(n) for the category Map and string parts array\n\nDATA STRUCTURES: Replaced Array.includes() with Map.has() for O(1) category membership checks. Used Map<string, TransactionRecord[]> for grouped category access. Used Set-like ordering preservation via separate categoryOrder array. Pre-computed medians stored in Map<string, number> for O(1) lookup during report generation.\n\nMEASUREMENT STRATEGY: The benchmark would show the isAboveThreshold function consuming >95% of execution time at scale (e.g., 10K+ transactions), since it's the only quadratic-or-worse operation. The string concatenation bottleneck becomes significant at very large report sizes but is secondary to the algorithmic issue.",
  "optimized_code": "import { formatCurrency, formatDate } from \"./formatters\";\nimport { TransactionRecord, CategorySummary } from \"./types\";\n\nexport function buildReport(transactions: TransactionRecord[]): string {\n  const parts: string[] = [\"=== Transaction Report ===\\n\\n\"];\n\n  // Group transactions by category using a Map — O(n) instead of O(n*k)\n  const categoryMap = new Map<string, TransactionRecord[]>();\n  const categoryOrder: string[] = [];\n\n  for (const tx of transactions) {\n    if (!categoryMap.has(tx.category)) {\n      categoryMap.set(tx.category, []);\n      categoryOrder.push(tx.category);\n    }\n    categoryMap.get(tx.category)!.push(tx);\n  }\n\n  // Precompute category medians once — O(n log n) total instead of O(n² log n)\n  const categoryMedians = new Map<string, number>();\n  for (const [cat, txs] of categoryMap) {\n    const amounts = txs.map(t => t.amount).sort((a, b) => a - b);\n    const mid = Math.floor(amounts.length / 2);\n    const median = amounts.length % 2 === 0\n      ? (amounts[mid - 1] + amounts[mid]) / 2\n      : amounts[mid];\n    categoryMedians.set(cat, median);\n  }\n\n  for (const cat of categoryOrder) {\n    parts.push(`Category: ${cat}\\n`);\n    parts.push(\"-\".repeat(40) + \"\\n\");\n\n    const catTransactions = categoryMap.get(cat)!;\n    let subtotal = 0;\n    const threshold = 97;\n    const median = categoryMedians.get(cat)!;\n    const flagLimit = median * (1 + threshold / 100);\n\n    for (const tx of catTransactions) {\n      parts.push(`  ${formatDate(tx.timestamp)} | ${tx.description.padEnd(30)} | ${formatCurrency(tx.amount)}\\n`);\n      subtotal += tx.amount;\n\n      if (tx.amount > flagLimit) {\n        parts.push(`  *** FLAGGED: amount exceeds category median by ${threshold}% ***\\n`);\n      }\n    }\n\n    parts.push(`  Subtotal: ${formatCurrency(subtotal)}\\n\\n`);\n  }\n\n  parts.push(\"=== End Report ===\\n\");\n  return parts.join(\"\");\n}"
}