Number of Distinct Integers in all Subarrays
Anonymous User
2543
ArrayOnline AssessmentCareer

Count the number of distinct integers in each subarray.

For Example:
[1,2,2,1]

The possible sub-arrays are:
[1] -> 1 Unique Element
[2] -> 1 Unique Element
[2] -> 1 Unique Element
[1] -> 1 Unique Element
[1,2] -> 2 Unique Elements
[2,2] -> 0 Unique Element
[2,1] -> 2 Unique Elements
[1,2,2] -> 1 Unique Element
[2,2,1] -> 1 Unique Element
[1,2,2,1] -> 0 Unique Element

So we should return 1+1+1+1+2+2+1+1 = 10

I'm not able to figure out how to solve this problem.
The time complexity must be less than O(n^2)

Comments (7)