A convoy of n vehicles crosses a line of border checkpoints in order; checkpoint i records the passport country code of the vehicle that passed it, given as nums[i]. For every index i (0-indexed) from 0 to n-1, define that checkpoint's balance as (the number of distinct country codes appearing among checkpoints 0..i, inclusive) minus (the number of distinct country codes appearing among checkpoints i+1..n-1; this is 0 when i is the last index). Compute the balance for every checkpoint, in order.
Line 1: a single integer n. Line 2: n space-separated integers nums_1 ... nums_n — the country codes recorded in checkpoint order.
n space-separated integers: the balance value for each checkpoint 0..n-1, in order.
1 <= n <= 10^5 1 <= nums_i <= 10^5
Example 1
Input
6 1 2 3 4 5 6
Expected
-4 -2 0 2 4 6
Explanation
All six codes are distinct. At i=0: prefix {1} has 1 distinct, suffix {2,3,4,5,6} has 5 distinct, balance=1-5=-4. At i=1: prefix {1,2}=2, suffix {3,4,5,6}=4, balance=-2. Continuing this pattern for every index gives -4 -2 0 2 4 6.
Example 2
Input
3 3 2 3
Expected
-1 1 2
Explanation
At i=0: prefix {3} has 1 distinct, suffix {2,3} has 2 distinct, balance=1-2=-1. At i=1: prefix {3,2}=2 distinct, suffix {3}=1 distinct, balance=1. At i=2: prefix {3,2,3}=2 distinct, suffix is empty=0, balance=2. Result: -1 1 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →