Dynamic Difference Pairs
MediumHash Map · Uber
You maintain a multiset of integers that starts empty. Each string in queries is one of:
"+x": insert one copy of the integerx."-x": delete one copy ofx. Ifxis not present, nothing happens.
Here x is a non-negative integer written in decimal (so "-5" means "delete a 5", never the number -5).
After each query, count the pairs of elements in the multiset whose values differ by exactly diff. Pairs are unordered and are counted by element, so equal values are separate elements: for example, {1, 1, 2} with diff = 1 has 2 pairs, and {4, 4, 4} with diff = 0 has 3 pairs.
Return a list with the count after every query.
Example 1
- Input:
- queries = ["+4", "+6", "+8", "+6", "-4", "-9"], diff = 2
- Output:
- [0, 1, 2, 4, 2, 2]
- Explanation
- After
+8the multiset is{4, 6, 8}with pairs (4,6) and (6,8). The second6adds two more pairs with 4 and 8, giving 4. Deleting4removes its two pairs, and-9changes nothing because 9 is absent.
Example 2
- Input:
- queries = ["+3", "+3", "+3", "-3"], diff = 0
- Output:
- [0, 1, 3, 1]
- Explanation
- With
diff = 0, pairs are equal values. Three 3s form 3 pairs; after one is deleted, two remain and form 1 pair.
Example 3
- Input:
- queries = ["+10", "+5", "+15"], diff = 5
- Output:
- [0, 1, 2]
- Explanation
15pairs only with10, and5pairs only with10, so after all three inserts there are 2 pairs.
Constraints
0 <= queries.length <= 10^5- Each query is
"+x"or"-x"with0 <= x <= 10^9 0 <= diff <= 10^9