performance-optimizer

Score Breakdown

Your Submission

{
  "explanation": "Three critical bottlenecks identified and resolved:\n\n1. **O(W*N) window filtering replaced with O(N) Map-based bucketing**: The original used `sorted.filter()` inside a loop over every window from minTime to maxTime. This scans ALL N events for EACH of W windows, giving O(W*N) total. I replaced this with a single-pass approach that computes each event's window index arithmetically using `Math.floor((timestamp - minTime) / windowSize) * windowSize`, bucketing into a Map. This is O(N) for all events and completely eliminates empty window iteration.\n\n2. **O(K^2) deduplication with Array.some() replaced with O(K) Set lookup**: The original `deduped.some(d => d.source === event.source && d.eventType === event.eventType)` performs a linear scan of the growing deduped array for every event, giving O(K^2) per window. I replaced this with a Set using a composite key (`source + '\\0' + eventType`) for O(1) amortized lookup, making deduplication O(K) per window.\n\n3. **Empty window iteration eliminated**: The original loop `for (let windowStart = minTime; windowStart <= maxTime; ...)` iterates over potentially many empty windows (e.g., sparse data with large gaps). The Map-based approach only stores and processes windows that contain events.\n\nData structure changes: Array.filter → Map bucketing, Array.some → Set lookup, Record<string,number> → Map<string,number> for typeCounts.\n\nOverall complexity improved from O(N log N + W*N + Σ(K²)) to O(N log N + N), where the sort dominates. For sparse data with many empty windows, this is a dramatic improvement.",
  "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 — O(N) instead of O(W*N)\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 — skips empty windows entirely\n  const sortedKeys: number[] = Array.from(windowMap.keys()).sort((a, b) => a - b);\n\n  for (const windowStart of sortedKeys) {\n    const windowEnd: number = windowStart + windowSize;\n    const windowEvents: EventRecord[] = windowMap.get(windowStart)!;\n\n    // Deduplicate using Set with composite key — O(K) instead of O(K^2)\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: string = 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: number = 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: string = \"\";\n    let maxCount: number = 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}"
}