# Sum of unique elements in all sub-arrays of an array

Given an array $$A$$, sum the number of unique elements for each sub-array of $$A$$. If $$A = \{1, 2, 1, 3\}$$ the desired sum is $$18$$.

Subarrays:

{1} - 1 unique element
{2} - 1
{1} - 1
{3} - 1
{1, 2} - 2
{2, 1} - 2
{1, 3} - 2
{1, 2, 1} - 2
{2, 1, 3} - 3
{1, 2, 1, 3} - 3


I have a working solution which sums the unique elements for all sub-arrays starting at index $$0$$, then repeats that process at index $$1$$, etc. I have noticed that for an array of size $$n$$ consisting of only unique elements, the sum I desire can be found by summing $$i(i + 1) / 2$$ from $$i = 1$$ to $$n$$, but I haven't been able to extend that to cases where there are non-unique elements. I thought I could use that fact on each sub-array, but my control logic becomes unwieldy. I've spent considerable time trying to devise a solution better than $$O(n^2)$$ to no avail. Is there one?

Secondary question: if there is no better solution, are there any general guidelines or hints to recognize that fact?

• An incremental algorithm is supposedly easier to come up with in this case, I think so. – Thinh D. Nguyen Oct 18 '18 at 7:16
• I don't understand the line {1, 2, 1} - 2. The multiset {1, 2, 1} only contains one unique element: 2. – Peter Taylor Oct 18 '18 at 10:28
• Peter, yes number of distinct elements might be better phrasing. If all elements of each sub-array are added to a set, the set size is the desired metric. In either case, the behavior in my example is what I'm looking for. – User12345654321 Oct 18 '18 at 17:34

Hint: Use an extra $$O(n)$$-spaced array of pointer to the last (biggest) index of each distinct value. Then, this array is very helpful when you do your above algorithm.

Lastly, we should have an $$O(n)$$ algorithm.

• This was a good hint. Assume zero-indexed arrays. Starting with sum = maxPossibleSum, iterate through the array adding elements to a set. If the added element is a duplicate, sum = sum - (indexPreviousOccurrence + 1) * (totalElements - currentIndex). This requires just one pass leading to O(n) like you said. Thanks for a quality nudge in the right direction. – User12345654321 Oct 18 '18 at 20:31

If the maximum number $$k$$ is not too high, a Counting Sort based solution can be used;

In the first step, we count the number of elements into the array $$C$$ by

for j = 1 to length(A)
C[A[j]] = C[A[j]]+1


now the array contains all the information we need to sum;

sum = 0;
for j = 1 to k
if C[i] > 1
sum =  C[i] * i


Complexity:

$$\mathcal{O}(n)$$ additions (increment) for the counting step

$$\mathcal{O}(n)$$ additions for the summation step

$$\mathcal{O}(n)$$ multiplications for the summation step

result $$\mathcal{O}(n)$$.

Note: indeed the multiplications are not necessary since we will have at most $$n-1$$ addition.

Let $$a_1,\ldots,a_m$$ be the distinct values. Now consider the positions of $$a_i$$'s in $$A$$. Assume the number of $$a_i$$'s is $$b_i$$ and the positions are as follows:

(x_{i0} non-a_i's) a_i (x_{i1} non-a_i's) a_i ... a_i (x_{ib_i} non-a_i's)


In your example $$A=\{1,2,1,3\}$$, when considering the value $$a_1=1$$, we have $$x_{10}=0,x_{11}=1,x_{12}=1$$ because the positions of $$1$$s are like 1 * 1 *: there is $$0$$ element before the first $$1$$, $$1$$ element between the first $$1$$ and the second $$1$$, and $$1$$ element after the second $$1$$.

Then there are \begin{align} &\sum_{j=0}^{b_i} \frac{x_{ij}(x_{ij}+1)}{2}\\ =\ &\frac{1}{2}\sum_{j=0}^{b_i}x_{ij}^2+\frac{1}{2}\sum_{j=0}^{b_i}x_{ij}\\ =\ &\frac{1}{2}\sum_{j=0}^{b_i}x_{ij}^2+\frac{1}{2}(n-b_i) \end{align} subarrays that do not contain $$a_i$$. Note there are $$n(n+1)/2$$ subarrays in total, so the final result we want is \begin{align} &\sum_{i=1}^m\left(\frac{n(n+1)}{2}-\frac{1}{2}\sum_{j=0}^{b_i}x_{ij}^2-\frac{1}{2}(n-b_i)\right)\\ =\ &\frac{1}{2}\left(mn^2+n-\sum_{i=1}^m\sum_{j=0}^{b_i}x_{ij}^2\right). \end{align}

To calculate $$\sum_{i=1}^m\sum_{j=0}^{b_i}x_{ij}^2$$, you can scan the array and maintain a lookup table that, for each distinct value, keeps the position of the last element with this value. With this table, when the $$(j+1)$$-th $$a_i$$ is scanned, you can compute $$x_{ij}$$ easily. This leads us to an $$O(n\log n)$$ solution (or $$O(n)$$ in average if you use a good hash table to implement the lookup table).

• could you clarify what X represents? It looks like a 2D array. This is the part I'm not understanding "(x_{i0} non-a_i's) a_i ..." – User12345654321 Oct 18 '18 at 17:17
• @User12345654321 In your example $A=\{1,2,1,3\}$, when considering the value $a_1=1$, we have $x_{10}=0,x_{11}=1,x_{12}=1$ because the positions of 1s are like 1 * 1 *: there is 0 element before the first 1, 1 element between the first 1 and the second 1, and 1 element after the second 1. – xskxzr Oct 19 '18 at 3:18