1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Are the numbers positive? $\endgroup$ Commented Dec 5, 2023 at 18:13
  • $\begingroup$ Yes, the numbers are positive. $\endgroup$ Commented Dec 5, 2023 at 18:28

1 Answer 1

6
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.