Find the smallest subarray with sum larger than a threshold

Question

Given a set of $n$ positive numbers $\{a_1,\ldots,a_n\}$ and a positive target $T$, find a subset $S$ from $\{a_1,\ldots,a_n\}$ of contiguous elements, that is $S=\{a_i,a_{i+1},a_{i+2},\ldots\}$ for some $i$, such that $|S|$ is minimum and $\sum_{a\in S}a\geq T$.

My algorithm is an exhaustive search one.

• Generate all subsets of contiguous elements from $\{a_1,\ldots,a_n\}$.
• Start with the lowest-cardinality subset $S$ and check the constraint $\sum_{a\in S}a\geq T$.

This gives $O(n^2)$ algorithm in the worst-case. Is there a better approach?

• Steven: Are the numbers positive?
• zebda: Yes, the numbers are positive.

Answer 1

You can solve your problem in linear time using a "sliding window" algorithm.

Let $i,j$ be two pointers initialized to 1ドル$, and denote by $\sigma(i,j)$ the sum $a_i + a_{i+1} + \dots + a_{j}$. As long as $i < n$ do the following:

• If $\sigma(i,j) <T$ and $j<n$, increment $j$ by 1ドル$.
• Otherwise, increment $i$ by 1ドル$.

Consider now all pairs of values $(i,j)$ attained by $i$ and $j$ during the previous procedure and, among those that satisfy $\sigma(i,j) \ge T$, return one that minimizes $j-i+1$.

Notice that the above algorithm can be implemented in time $O(n)$ since there are at most 2ドルn-1$ considered pairs $(i,j)$ (each index can be incremented at most $n-1$ times) and you can update the value of $\sigma(i,j)$ in constant time whenever $i$ or $j$ changes (subtract $a_{i}$ just before incrementing $i$, and add $a_j$ immediately after incrementing $j$).

We only need to show that some pair considered $(i,j)$ corresponds to the endpoints $i^*, j^*$ of an optimal subarray $a_{i^*}, a_{i^*+1}, \dots, a_{j^*}$. At some point during the execution of the algorithm we must either have $i = i^*$ or $j=j^*$. Consider the first iteration when this happens.

• If $i=i^*$ then $j \le j^*$. Moreover, for all $j' \in \{j, j+1, \dots, j^*-1\}$ (this set might be empty), we have $\sigma(i, j') < T$ and hence $j$ gets incremented until $j=j^*$ while $i$ remains unchanged. Therefore $(i^*, j^*)$ is considered.

• If $j=j^*$ then $i \le i^*$. Moreover, for all $i' \in \{i, i+1,\dots, i^*-1\}$ (this set might be empty), we have $\sigma(i', j) \ge T$ and hence $i$ gets incremented until $i=i^*$ while $j$ remains unchanged. Therefore $(i^*, j^*)$ is considered.

• zebda: When $i$ increments, $j$ should be set to $i,ドル right?
• Steven: No. When $i$ increments leave $j$ to its previous value. Exactly one pointer increments in each iteration. The other is unaffected.
• zebda: In the case $[5, 10, 1, 8, 13],ドル and $T=21$. I will start with $\sigma(1,1)=5,ドル then increment $j=2$. Now, I have $\sigma(1,2)=15$ and $j$ increments until $j$ reaches $j=4$. Now $i$ increments and we have $i=2$ and $j=4$ and then $j$ keeps increasing. I will never check $\sigma(2,2),ドル right? But I guess that's useless to check, right?
• zebda: I think the algorithm should run while $i\leq n$ instead of $i<n$.
• Steven: Yes, in your example $i=2, j=2$ never happens. That's expected, since the algorithm runs in linear time only $O(n)$ of the $\Omega(n^2)$ possible pairs of indices $i, j$ will be encountered. If you use while $i \le n$ then the last iteration will increment $i$ from $n$ to $n+1,ドル which is out of bounds.