# Find the smallest subarray with sum larger than a threshold

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?

• Are the numbers positive? Commented Dec 5, 2023 at 18:13
• Yes, the numbers are positive. Commented Dec 5, 2023 at 18:28

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) and $$j, 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 $$2n-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.

• When $i$ increments, $j$ should be set to $i$, right? Commented Dec 5, 2023 at 18:50
• No. When $i$ increments leave $j$ to its previous value. Exactly one pointer increments in each iteration. The other is unaffected. Commented Dec 5, 2023 at 18:52
• 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? Commented Dec 5, 2023 at 19:08
• I think the algorithm should run while $i\leq n$ instead of $i<n$. Commented Dec 5, 2023 at 19:15
• 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. Commented Dec 5, 2023 at 19:39