2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Great, thanks for the answer. This should be the best way to do it, right ? if instead $i$ is given as a query $q$ times, can't we find an asymptotically faster algorithm ? $\endgroup$ – Noctisdark Aug 2 '17 at 21:43
  • 2
    $\begingroup$ It seems like you actually had a different question in mind. You should ask it as a new question, or better yet, first spend a few hours trying to solve it yourself. $\endgroup$ – Yuval Filmus Aug 2 '17 at 21:54

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.