Optimize the code · Easy

Speed Up the Active-Customer Join

Easy Make it fast Most askedSeen at Shopify, Stripe

A reporting job counts how many orders were placed by active customers. countActiveOrders(activeIds, orderUserIds) receives the IDs of active customers and, for every order, the ID of the customer who placed it. It returns the number of orders placed by active customers.

The code reads naturally, but the nightly run now has 100,000 active customers and 200,000 orders and has started timing out. Make it fast without changing the results.

Example 1

Input: activeIds = [1, 3], orderUserIds = [1, 2, 3, 3, 4]
Output: 3

The slow code

Every case must finish within 300 ms (budgets are per language in the editor).

function countActiveOrders(activeIds, orderUserIds) {
  let count = 0;
  for (const userId of orderUserIds) {
    if (activeIds.includes(userId)) count++;
  }
  return count;
}

function countActiveOrders(activeIds: number[], orderUserIds: number[]): number {
  let count = 0;
  for (const userId of orderUserIds) {
    if (activeIds.includes(userId)) count++;
  }
  return count;
}

def count_active_orders(active_ids: list[int], order_user_ids: list[int]) -> int:
    count = 0
    for user_id in order_user_ids:
        if user_id in active_ids:
            count += 1
    return count

<?php

function countActiveOrders(array $activeIds, array $orderUserIds): int
{
    $count = 0;
    foreach ($orderUserIds as $userId) {
        if (in_array($userId, $activeIds, true)) {
            $count++;
        }
    }
    return $count;
}

class Solution {
    public int countActiveOrders(int[] activeIds, int[] orderUserIds) {
        int count = 0;
        for (int userId : orderUserIds) {
            for (int id : activeIds) {
                if (id == userId) {
                    count++;
                    break;
                }
            }
        }
        return count;
    }
}

Hints

Hint 1

What does includes / in / in_array cost on an array?

Hint 2

This is a join. What does a database do to join two large tables without comparing every pair?

Make it faster

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(a + o) · Space O(a)

Why it is slow: activeIds.includes(id) (id in active_ids, in_array) scans the array: O(a) per order and O(a x o) in total, about 15 billion comparisons here. The loop looks linear because the inner loop is hidden inside a library call.

The fix: build a hash set of the active IDs once (O(a)), then each order is an O(1) lookup: O(a + o) in total. This is exactly a database hash join: build a hash table on the smaller input, probe it with the larger one.

In a real system the better fix may be to do the join in the database (JOIN or WHERE user_id IN (SELECT ...) with an index), so the rows never travel to the application.

Optimized solution

function countActiveOrders(activeIds, orderUserIds) {
  const active = new Set(activeIds); // build once: O(a)
  let count = 0;
  for (const userId of orderUserIds) if (active.has(userId)) count++; // probe: O(1) each
  return count;
}

function countActiveOrders(activeIds: number[], orderUserIds: number[]): number {
  const active = new Set(activeIds); // build once: O(a)
  let count = 0;
  for (const userId of orderUserIds) if (active.has(userId)) count++; // probe: O(1) each
  return count;
}

def count_active_orders(active_ids: list[int], order_user_ids: list[int]) -> int:
    active = set(active_ids)  # build once: O(a)
    return sum(1 for user_id in order_user_ids if user_id in active)  # probe: O(1) each

<?php

function countActiveOrders(array $activeIds, array $orderUserIds): int
{
    $active = array_flip($activeIds); // id => position, built once
    $count = 0;
    foreach ($orderUserIds as $userId) {
        if (isset($active[$userId])) {
            $count++;
        }
    }
    return $count;
}

class Solution {
    public int countActiveOrders(int[] activeIds, int[] orderUserIds) {
        Set<Integer> active = new HashSet<>();
        for (int id : activeIds) active.add(id);
        int count = 0;
        for (int userId : orderUserIds) if (active.contains(userId)) count++;
        return count;
    }
}

Common mistakes

Recreating the set inside the loop.
PHP: in_array is linear; use the IDs as array keys (array_flip) and isset.

Follow-up questions

The two lists come from two different services and do not fit in memory: what now? (sort-merge join, or partition by hash)
Do it in SQL and explain which index the query needs.

Speed Up Contains Duplicate · Easy
Speed Up Two Sum · Easy
Speed Up Recursive Fibonacci · Easy
Speed Up the Most Frequent Word · Easy
Speed Up Range Sum Queries · Medium
Speed Up Longest Consecutive Sequence · Medium