Number of occurrences in contiguous subarrays 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_.

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]$