Array of Subarrays
UptoSkills Arena is organizing a coding challenge. As a warm-up, participants are given an array of integers and asked to find the number of subarrays that contain only unique elements. A subarray is a contiguous part of the array. For example, in [1, 2, 3], [1, 2] and [2, 3] are subarrays, but [1, 3] is not. Help us count these unique-element subarrays!
Input
The first line contains an integer n, the size of the array. The second line contains n integers, the elements of the array.
Output
Print a single integer: the total count of subarrays with unique elements.
Constraints
1 <= n <= 200000 Elements of the array are integers between -10^9 and 10^9.
Example 1
5 1 2 3 2 1
11
Subarrays with unique elements are: [1], [2], [3], [2], [1], [1, 2], [2, 3], [3, 2], [2, 1], [1, 2, 3], [2, 3, 2](invalid), [3, 2, 1]. Total = 11.
Example 2
3 1 1 1
3
Subarrays with unique elements are: [1], [1], [1]. Total = 3.
Hints
Similar problems
- Count Subarrays with Distinct ElementsMedium
- Longest Subarray with At Most K Distinct ElementsMedium
- Count Unique Element PairsMedium
- Longest Subarray with Distinct ElementsHard
- Distinct Subarrays with Bounded SumHard
- Longest Subarray with Equal Number of Zeroes and OnesHard
More topics: Hash Map and Hashing problems, Two Pointers problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 1 2 3 2 1
3 1 1 1