Find the minimum count of elements summing to a pre-defined sum

Question

We have the following problem: Given an array of integers $\{a_1, a_2,...,a_n\}$ and a number $s$, find a contiguous sub-array of elements that sum exactly to $s$. If multiple solutions exist, find a solution that is smallest in terms of length (length of sub-array). If there is no such contiguous sub-array, output "-1".

I have thought of an $O(n^2)$ algorithm, using two pointers and prefix sums, but I cannot find an $O(n)$ algorithm. What would an $O(n)$ algorithm be like?

Answer 1

This can be solved in $O(n \lg n)$ time by computing prefix sums and then using divide-and-conquer.

Step 1. Compute the prefix sums $p_0,p_1,\dots,p_n$, where we define $p_i = a_1 + a_2 + \dots + a_i$. Throw away the $a_i$'s. Now the problem becomes: count how many index-pairs $i,j$ there are where $0 \le i \le j \le n$ and $p_j = p_i + s$.

Step 2. Solve this problem using divide-and-conquer. First, count the number of solutions where $0 \le i \le j \le n/2$ (recursively). Second, count the number of solutions where $n/2 < i \le j \le n$ (recursively). Third, count the number of solutions where $0 \le i \le n/2$ and $n/2 < j \le n$. This third step can be done in $O(n)$ time (expected running time). Since this is your exercise, I'll let you work out how: it's not too hard.

The total running time satisfies the recurrence $T(n) = 2 T(n/2) + O(n)$, so this yields a $O(n \lg n)$ time solution.

Answer 2

This algorithm is $O(n)$ only for non-negative integers, $O(n~log~n)$ otherwise. I think there is no $O(n)$ solution for mixed positive/negative numbers, though I cannot formally prove it.

First, calculate the cumulative sum over the array. This yields an array of length $n+1$

$$\{b_1,b_2,...,b_{n+1}\} = \{0, a_1,a_1+a_2,...\}$$

and allows the calculation of any sum over a range $i..j$ in constant time as $b_{j+1}-b_i$.

If all $a_i$ are non-negative, $\{b_1,b_2,...\}$ is already monotonic. If this is not the case, sort it. Also store the array of indices.

Now you can start with two pointers, called $p_1$ and $p_2$, both initialized to $b_1$. Perform the following algorithm:

• If the sum over the range is too large, move $p_1$ one step forward.
• If the sum over the range is too small, move $p_2$ one step forward.

• If the sum over the range is exactly $s$, you found a solution.

  • Store it (if the element count is smaller than that of the currently best solution).
  • If the element in front of the trailing pointer is equal to the current one, move the trailing pointer one step forward. Otherwise move the leading pointer.
  • You can get range over which you calculated the sum by subtracting the indices. This range can be either ascending or descending, dependent on whether the element were swapped during sort.

Both the cumulative sum and the search require exactly one pass over the array, so the algorithm is of time complexity $O(n)$ for non-negative numbers. In the general case, a sort is required which results in a complexity of $O(n~log~n)$.

Example

s=1
a=[1, -1, 1, -1]

Calculate the prefix sums:
b=[0, 1, 0, 1, 0]

Sort b, keep track of the original indices.
b=[0, 0, 0, 1, 1]
i=[1, 3, 5, 2, 4]

Use the two-pointer method
b=[0, 0, 0, 1, 1]
p1 ^
p2 ^
p2 - p1 = 0 < 1     => rule 2

b=[0, 0, 0, 1, 1]
p1 ^
p2    ^
p2 - p1 = 0 < 1     => rule 2

b=[0, 0, 0, 1, 1]
p1 ^
p2       ^
p2 - p1 = 0 < 1     => rule 2

b=[0, 0, 0, 1, 1]
p1 ^
p2          ^
p2 - p1 = 1 == 1    => rule 3
Look up indices
i=[1, 3, 5, 2, 4]
p1 ^
p2          ^
=> solution: sum from 1 inclusive to 2 exclusive is 1
=> length of solution is 2 - 1 = 1 (accept)

b=[0, 0, 0, 1, 1]
p1    ^
p2          ^
p2 - p1 = 1 == 1    => rule 3
Look up indices
i=[1, 3, 5, 2, 4]
p1    ^
p2          ^
=> solution: sum from 3 exclusive down to 2 inclusive is 1
=> length of solution is 2 - 3 = -1 (we already have a solution of length 1 => reject)

b=[0, 0, 0, 1, 1]
p1       ^
p2          ^
p2 - p1 = 1 == 1    => rule 3
Look up indices
i=[1, 3, 5, 2, 4]
p1       ^
p2          ^
=> solution: sum from 5 exclusive down to 2 inclusive is 1
=> length of solution is 2 - 5 = -3 (we already have a solution of length 1 => reject)

b=[0, 0, 0, 1, 1]
p1       ^
p2             ^
p2 - p1 = 1 == 1    => rule 3
Look up indices
i=[1, 3, 5, 2, 4]
p1       ^
p2             ^
=> solution: sum from 5 exclusive down to 4 inclusive is 1
=> length of solution is 4 - 5 = -1 (we already have a solution of length 1 => reject)

b=[0, 0, 0, 1, 1]
p1          ^
p2             ^
p2 - p1 = 0 < 1     => rule 2

rule 2 not applicable: pointer reached end, terminate.

The final solution is: sum from 1 inclusive to 2 exclusive, length 1