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$
    – Steven
    Commented Dec 5, 2023 at 18:13
  • $\begingroup$ Yes, the numbers are positive. $\endgroup$
    – zebda
    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$
    – zebda
    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$
    – Steven
    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$
    – zebda
    Commented Dec 5, 2023 at 19:08
  • $\begingroup$ I think the algorithm should run while $i\leq n$ instead of $i<n$. $\endgroup$
    – zebda
    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$
    – Steven
    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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.