Solving N² Complexity with JavaScript Maps

As developers, we often encounter situations where we need to find relationships between elements in different arrays. The immediate solution that comes to mind is usually nested loops, leading to O(n²) complexity. However, beyond poor performance, there’s a more serious problem: in high-traffic environments, an O(n²) algorithm can block the event loop and freeze your server.

Let's explore a real-world example and see how we can dramatically improve performance using JavaScript Maps.

The N² Problem

Consider this common scenario where we need to match users with their orders:

const users = [
  { id: 1, name: 'Alice' },
  { id: 2, name: 'Bob' },
  // ... potentially thousands of users
]

const orders = [
  { userId: 1, product: 'Laptop' },
  { userId: 2, product: 'Phone' },
  // ... potentially thousands of orders
]

// Inefficient O(n²) solution
const getUserOrders = () => {
  return users.map((user) => {
    const userOrders = orders.filter((order) => order.userId === user.id)
    return {
      ...user,
      orders: userOrders,
    }
  })
}

With this approach, for each user, we're scanning through the entire orders array. If we have 1,000 users and 1,000 orders, we're performing 1,000,000 comparisons!

The Bigger Problem: Blocking the Event Loop

JavaScript runs on a single thread, meaning the event loop is responsible for processing all tasks, from handling HTTP requests to database queries. When a computationally expensive operation like an O(n²) loop takes too long, it blocks the event loop, causing the server to stop responding to incoming requests. This can result in:

• Delayed Responses: Other users experience increased latency.
• Server Freezes: Requests can time out, degrading the user experience.
• Wasted Resources: In a microservices architecture, a frozen service may trigger cascading failures.

This is why solving O(n²) complexity isn’t just about optimizing performance—it’s about keeping your application responsive and stable.

The Map Solution

Here's how we can solve this using a Map to achieve O(n) complexity:

const getUserOrdersEfficient = () => {
  // Create a Map of orders indexed by userId
  const orderMap = new Map()
  orders.forEach((order) => {
    if (!orderMap.has(order.userId)) {
      orderMap.set(order.userId, [])
    }
    orderMap.get(order.userId).push(order)
  })

  // Now we can look up orders directly by userId
  return users.map((user) => ({
    ...user,
    orders: orderMap.get(user.id) || [],
  }))
}

Performance Comparison

Let's look at the actual performance difference:

// Test with larger datasets
const generateTestData = (size) => {
  const users = Array.from({ length: size }, (_, i) => ({
    id: i + 1,
    name: `User${i + 1}`,
  }))
  const orders = Array.from({ length: size }, (_, i) => ({
    userId: Math.floor(Math.random() * size) + 1,
    product: `Product${i + 1}`,
  }))
  return { users, orders }
}

const { users, orders } = generateTestData(10000)

console.time('N² Solution')
getUserOrders()
console.timeEnd('N² Solution')
// N² Solution: ~500ms

console.time('Map Solution')
getUserOrdersEfficient()
console.timeEnd('Map Solution')
// Map Solution: ~5ms

Why Maps Are Better Here

1. Single Pass Processing: We only need to iterate through each array once
2. O(1) Lookups: Map provides constant-time access to stored values
3. Memory Efficient: We're trading a small amount of memory for massive performance gains
4. Scalability: Performance remains linear as data size grows

Best Practices for Using Maps

When implementing this pattern, keep in mind:

1. Pre-size Your Maps: If you know the size of your data, you can optimize memory allocation:

const orderMap = new Map()
orderMap.set(user.id, [])

2. Clear References: When you're done, clear the Map to help garbage collection:

orderMap.clear()

Conclusion

Next time you find yourself writing nested loops, stop and consider if a Map-based solution might be more appropriate. The small effort of restructuring your data can lead to dramatic performance improvements, especially as your datasets grow.

Remember:

• Nested loops are often a red flag for performance issues
• Maps provide O(1) lookup time
• O(n²) algorithms can block the event loop and freeze the server
• The extra memory usage is usually worth the performance gain
• Always measure performance with realistic data sizes

By making smart choices about data structures, we can write code that not only works but scales efficiently with our applications' growth.