4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ An incremental algorithm is supposedly easier to come up with in this case, I think so. $\endgroup$ – Thinh D. Nguyen Oct 18 '18 at 7:16
  • $\begingroup$ I don't understand the line {1, 2, 1} - 2. The multiset {1, 2, 1} only contains one unique element: 2. $\endgroup$ – Peter Taylor Oct 18 '18 at 10:28
  • $\begingroup$ 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. $\endgroup$ – User12345654321 Oct 18 '18 at 17:34
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – User12345654321 Oct 18 '18 at 20:31
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ 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 ..." $\endgroup$ – User12345654321 Oct 18 '18 at 17:17
  • $\begingroup$ @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. $\endgroup$ – xskxzr Oct 19 '18 at 3:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.