Distinct Elements in Prefix
MediumPractice library · +20 XParrayshash setprefix sums
Given an array of N integers, for each element at index i (from 0 to N-1), calculate the number of distinct integers in the subarray from index 0 to i, inclusive. Print these counts, separated by spaces.
Input
The first line contains an integer N (1 <= N <= 200000). The second line contains N space-separated integers a_0, a_1, ..., a_{N-1} (-10^9 <= a_i <= 10^9).
Output
Print N space-separated integers, where the k-th integer is the count of distinct elements in the prefix of length k (i.e., a_0, ..., a_{k-1}).
Constraints
1 <= N <= 200000, -10^9 <= a_i <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
5 1 2 1 3 2
Output
1 2 2 3 3
Prefixes are [1], [1,2], [1,2,1], [1,2,1,3], [1,2,1,3,2]. Distinct counts are 1, 2, 2, 3, 3.
Example 2
Input
3 5 5 5
Output
1 1 1
Prefixes are [5], [5,5], [5,5,5]. Distinct counts are 1, 1, 1.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 1 2 1 3 2
Example 2 input
3 5 5 5