Number of occurrences in contiguous subarrays

Question

How to count the number of occurrences of each element in all contiguous subarrays?

For an array $[1,2,3]$, the contiguous subarrays are:

$[1]$, $[2]$, $[3]$
$[1,2]$, $[2,3]$
$[1,2,3]$

$1$ occurs $3$ times, $2$ occurs $4$ times and $3$ occurs $3$ times.

can the array contain repeated elements? Do you want an algorithm? What is the complexity you are hoping to achieve? — Asinomás, Sep 25 '16 at 19:55
@JorgeFernándezHidalgo I am expecting the answer to be related for all elements. But if it's not yeah, O(1) per element. — xyz, Sep 25 '16 at 20:13
@Jean-ClaudeArbaut Yes, same question, but I hadn't seen that question. — xyz, Sep 26 '16 at 09:40
@Jean-ClaudeArbaut I arrived at the same result you did $u(n,k)=\sum_{i=1}^k\sum_{j=k}^n (j-i+1) 2^{\max(0,i-2)+\max(0,n-j-1)}$, but I could not boil it down to $O(n)$ :( — xyz, Sep 26 '16 at 09:49

score 4 · Accepted Answer · answered Sep 25 '16 at 20:16

4

Suppose that our array is: $[1,2,3\dots ,n]$. How many contiguous subarrays contain $k$? Look at the following drawing:

$|1|2|3|4|\dots |k-1|k|k+1|\dots |n|$.

Every subarray containing $k$ can be obtained by selecting a "barrier" to the left of $k$ and a barrier to the right of $k$. There are $k$ barriers to the left of $k$ and $n-k+1$ barriers to the right of $k$.

Therefore there are $k(n-k+1)$ contiguous subarrays containing $k$ in the array $[1,2,3\dots n]$

answered Sep 25 '16 at 20:16

Asinomás

105,651

Thanks! I found another way to arrive at the result, though yours is much concise! – xyz Sep 25 '16 at 20:39
@prakharsingh95 you're welcome, happy to help. – Asinomás Sep 25 '16 at 20:40

Gnuk · Answer 2 · 2016-09-25T20:26:15.327

You grouped the continguous subarrays by length already: this is quite useful!

For example, if we take the array [1,2,3,4]:

[1], [2], [3], [4] (all numbers occur once)
[1, 2], [2, 3], [3, 4] (1 and 4 occur once, 2 and 3 occur twice)
[1, 2, 3], [2, 3, 4] (1 and 4 occur once, 2 and 3 occur twice)
[1, 2, 3, 4] (all numbers occur once)

There are a lot of things to notice here, of which I will state a couple:

1 and 4 have the same number of occurences, just like 2 and 3.
1 and 4 (more generally, 1 and $n$) occur exactly once in the continguous subarrays of a certain length.
2 and 3 occur once, then twice, twice again, then once again.

Try this yourself for [1,2,3,4,5]. Do you notice anything? Can you generalise this?

That line "once twice, twice, once again' was most helpful. Arrived at @JorgeFernándezHidalgo answer — xyz, Sep 25 '16 at 20:26

xyz · Answer 3 · 2016-09-25T20:44:22.300

In addition to @JorgeFernándezHidalgo answer, here's another way to arrive at the result, (thanks @HarrySmit for helping out):

All the results for subarrays of size till $N/2$ are duplicated in subarrays of greater size ($[1,2,3,4]$ has the same elements as $[1]$,$[2]$,$[3]$,$[4]$, subarrys of size $2$ contain the same elements as subarrays of size $N-1$ and so on).

Also note that an element at index $k$ occurs $n$ times in subarrays of length $1$ to $n$, and $k$ times in bigger subarrays (till length $N/2$).

So the total number of occurrences in all subarrays upto length $N/2$ is $1+2+...+k + (N/2-k)*k = k(N-k+1)/2$.

This result is replicated in subarrays of length greater than $N/2$, so we multiply by $2$, the final result being $k(N-k+1)$.

Number of occurrences in contiguous subarrays

3 Answers3