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.
$\endgroup$ 73 Answers
$\begingroup$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]$
$\endgroup$ 2 $\begingroup$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?
$\endgroup$ 1 $\begingroup$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)$.
$\endgroup$
