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

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