performance-optimizer

Score Breakdown

Your Submission

{
  "explanation": "Three key bottlenecks identified and fixed:\n\n1. **O(W×N) window filtering → O(N) single-pass bucketing**: The original code used `sorted.filter()` inside the window loop, scanning ALL N events for EACH of W windows. This is O(W×N). Replaced with a single-pass Map-based bucketing approach that computes each event's window index arithmetically in O(1), giving O(N) total for assignment.\n\n2. **O(K²) deduplication with `.some()` → O(K) with Set**: The original used `deduped.some()` which is O(K) per event within a window, giving O(K²) per window. Replaced with a Set using composite key `source + '\\0' + eventType` for O(1) lookup, making deduplication O(K) per window.\n\n3. **Iteration over empty windows eliminated**: The original loop iterated from minTime to maxTime in windowSize steps, processing empty windows. The new approach only processes windows that contain events by using a Map, skipping gaps entirely.\n\nOverall complexity improved from O(N log N + W×N + sum(K²)) to O(N log N + N), where the sort dominates. Data structures changed: Array.filter → Map bucketing, Array.some → Set lookup, Object typeCounts → Map.",
  "optimized_code": "import { EventRecord, ProcessedBatch } from \"./types\";\n\nexport function processEvents(\n  events: EventRecord[],\n  windowSize: number\n): ProcessedBatch[] {\n  if (events.length === 0) return [];\n\n  const sorted = events.slice().sort((a, b) => a.timestamp - b.timestamp);\n  const minTime = sorted[0].timestamp;\n\n  // Single pass: bucket events into windows using Map\n  const windowMap = new Map<number, EventRecord[]>();\n\n  for (const event of sorted) {\n    const windowStart = minTime + Math.floor((event.timestamp - minTime) / windowSize) * windowSize;\n    let bucket = windowMap.get(windowStart);\n    if (!bucket) {\n      bucket = [];\n      windowMap.set(windowStart, bucket);\n    }\n    bucket.push(event);\n  }\n\n  const batches: ProcessedBatch[] = [];\n\n  // Process each non-empty window\n  const sortedKeys = Array.from(windowMap.keys()).sort((a, b) => a - b);\n\n  for (const windowStart of sortedKeys) {\n    const windowEnd = windowStart + windowSize;\n    const windowEvents = windowMap.get(windowStart)!;\n\n    // Deduplicate using Set with composite key\n    const seen = new Set<string>();\n    const deduped: EventRecord[] = [];\n    const typeCounts = new Map<string, number>();\n\n    for (const event of windowEvents) {\n      const key = event.source + '\\0' + event.eventType;\n      typeCounts.set(event.eventType, (typeCounts.get(event.eventType) || 0) + 1);\n      if (!seen.has(key)) {\n        seen.add(key);\n        deduped.push(event);\n      }\n    }\n\n    if (deduped.length === 0) continue;\n\n    let totalValue = 0;\n    const sources = new Set<string>();\n    for (const e of deduped) {\n      totalValue += e.value;\n      sources.add(e.source);\n    }\n\n    let dominantType = \"\";\n    let maxCount = 0;\n    for (const [type, count] of typeCounts) {\n      if (count > maxCount) {\n        maxCount = count;\n        dominantType = type;\n      }\n    }\n\n    batches.push({\n      windowStart,\n      windowEnd,\n      eventCount: deduped.length,\n      totalValue: Math.round(totalValue * 100) / 100,\n      uniqueSources: sources.size,\n      dominantType,\n      duplicatesRemoved: windowEvents.length - deduped.length,\n    });\n  }\n\n  return batches;\n}"
}