Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I've recently been thinking about this problem.
Given an array $A$ containing $n$ integers and an index $i$, find the number of subgements of $A$ containing $A[i]$ as their minimum.
To better illustrate the problem, consider the array $A = [5, 1, 7]$ and we want to find the number of subsegments containing $A[1] = 1$ as their minimum. Clearly the answer is 4 and we can easily enumerate them: $[1], [5, 1],[5, 1, 7], [1, 7]$.
What the fastest way to compute the number of subsegments?
You haven't stated what a subsegment is, but I assume that you mean a "contiguous subsequence", that is, $A[s],A[s+1],\ldots,A[t]$. Also, I'm assuming that $A[i]$ is still a minimum if there are other equal values (you can easily adapt the algorithm for the other option).
Let $\ell \leq i$ be the smallest index such that $A[s] \leq A[i]$ for all $\ell \leq s \leq i$, and let $r \geq i$ be the largest index such that $A[r] \leq A[i]$ for all $i \leq s \leq r$. Then $A[i]$ is a minimum of $A[s],\ldots,A[t]$ iff $\ell \leq s$ and $t \leq r$. Thus there are $i-\ell+1$ options for $s$, namely $\ell,\ell+1,\ldots,i$, and similarly $r-i+1$ options for $t$, for a total of $(i-\ell+1)(r-i+1)$.
You can easily find $\ell,r$ in linear time by scanning left of and right of $i$ (respectively), so this algorithm runs in linear time.
