Loading page…
Practice problem · easy
An online store keeps a list of today's orders. Each entry is the id of the customer who placed one order, so a customer who ordered three times appears three times.
Support agents open customer pages all day and ask, for one customer id, how many orders that customer placed today. You answer a whole batch of such questions at once.
Write count_orders(customers, queries).
customers[i] is the customer id of the i-th order today.queries[j] is a customer id an agent asks about.customers has 0 orders.Input: customers = [5, 9, 5, 5], queries = [5, 7]
Output: [3, 0]The trace builds a table of order counts, then answers the queries from it.
| Step | Read | Counts after |
|---|---|---|
| 1 | customer 5 | 5: 1 |
| 2 | customer 9 | 5: 1, 9: 1 |
| 3 | customer 5 | 5: 2, 9: 1 |
| 4 | customer 5 | 5: 3, 9: 1 |
| 5 | query 5 | answer 3 |
| 6 | query 7 | answer 0 |
Customer 5 has three orders, and customer 7 has none, so the output is [3, 0].
Input: customers = [], queries = [4, 8]
Output: [0, 0]Nobody ordered, so every answer is 0.
Input: customers = [2, 3, 2], queries = [3, 2]
Output: [1, 2]Customer 2 appears twice and customer 3 once, and the answers follow the order of the queries.
0 ≤ customers.length ≤ 100,000 (orders today)0 ≤ queries.length ≤ 100,000 (questions in the batch)1 ≤ customers[i], queries[j] ≤ 10^6 (customer ids)Counting each query by scanning all the orders costs n × q steps. With 100,000 of each, that is 10^10 steps, far over the budget of about 10^8 a second. A table of counts is built in n steps, and each query then costs one step.
count_orders · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.