Loading page…
Practice problem · easy
An online store links two products when customers often buy them together. The store has n products, numbered 0 to n - 1, and a list of links. A link is a pair [a, b], and it works both ways.
You work on the "Bought together" shelf. To decide which products get a shelf, you want to know how many other products each product is linked with.
Write link_counts(n, pairs).
n is the number of products.pairs[i] = [a, b] is a link between product a and product b. Each link is listed once, and no product is linked to itself.n numbers. The number at position i is how many products product i is linked with. A product with no links gets 0.Input: n = 5, pairs = [[0, 1], [0, 2], [1, 2], [3, 2]]
Output: [2, 2, 3, 1, 0]| Product | Links that name it | Count |
|---|---|---|
| 0 | [0, 1], [0, 2] |
2 |
| 1 | [0, 1], [1, 2] |
2 |
| 2 | [0, 2], [1, 2], [3, 2] |
3 |
| 3 | [3, 2] |
1 |
| 4 | none | 0 |
Each link counts once for each of its two products.
Input: n = 3, pairs = []
Output: [0, 0, 0]There are no links, so every count is 0.
Input: n = 2, pairs = [[0, 1]]
Output: [1, 1]One link touches both products, so each has a count of 1.
1 ≤ n ≤ 10^50 ≤ length of pairs ≤ 2 · 10^50 ≤ a, b < n, a ≠ b, and each link appears onceThere can be 100,000 products and 200,000 links. Scanning every link for each product would be 100,000 times 200,000 steps, about twenty billion. That is far too slow.
Each link names exactly two products, so one pass over the links, adding one to two counters, is enough.
link_counts · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.