Count as you go
Use the counts so far to count matching pairs in one pass. About 8 minutes.
Stand at each value and look back
At a reunion, everyone shakes hands with each old classmate from their year. How many handshakes? One way to count: as each person arrives, they shake hands with everyone from their year who's already there.
Counting equal pairs works the same way. Walk the list, and at each value ask: how many copies of this value came before me? Each of them makes a pair with this one. A map of counts so far answers that in one lookup.
No 2s before. pairs = 0, then seen = {2: 1}.
Ask first, then add yourself
Order matters. First add the number of earlier copies to the answer. Then add 1 to this value's count, so that later copies can pair with this one.
Do it the other way round and every value pairs with itself. And use a 64-bit number for the answer: a million equal values make about 500 billion pairs.
seen = {}
pairs = 0
for x in nums:
pairs += seen.get(x, 0)
seen[x] = seen.get(x, 0) + 1
return pairsCounting equal pairs in 7, 7, 7, what gets added at each position?
- A0, then 1, then 2 (3 in total)
- B1, then 2, then 3 (6 in total)
- C3 each time (9 in total)
Show the answer
0, then 1, then 2 (3 in total). Each 7 pairs with every 7 before it: 0 + 1 + 2 = 3.
Count equal pairs
Return how many pairs of positions i < j have nums[i] == nums[j].
nums = [2, 2, 5, 2] → 3
0 ≤ n ≤ 500,000 · −1,000,000,000 ≤ each value ≤ 1,000,000,000 · return a long