3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What do you mean by "minimum count of continuous array elements that sum exactly as $s$"? Can you explain the problem statement a bit more clearly? Break it down into smaller pieces, please: I think you've tried to be too sparing in your use of English words. $\endgroup$ – D.W. Feb 18 '16 at 3:00
  • $\begingroup$ Also, what makes you think that a $O(n)$ time algorithm exists? What is the context in which you encountered this problem? Is it an exercise in a textbook, and if so, which chapter? (which techniques has it introduced by this point in the textbook?) $\endgroup$ – D.W. Feb 18 '16 at 3:17
  • $\begingroup$ @D.W. It is a general exercise in the textbook (a local one, so it is not famous...) and therefore, there are no techniques to be used. However, the problem statement imposes positive numbers everywhere, but I would also like (for practice) to extend it to negative numbers too. Example: $s=5$ $\{1, 2, 1, 4, 2, 1\}$ then the result is 2 that is the continuous subsequence $\{1, 4\}$. $\endgroup$ – Jason Feb 18 '16 at 6:18
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Another approach: After you calculate the prefix sums, for each $p_i$ you could try to find a suitable $p_j$ with binary search, so that $p_j = p_i + s$. The downside of this approach is that is only works for non-negative $a_i$ elements, which would allow constructing a non-decreasing prefix array. This works in $O(nlogn)$, too. :) $\endgroup$ – Konstantin Yovkov Feb 18 '16 at 13:08
0
$\begingroup$

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
$\endgroup$
  • $\begingroup$ You are not allowed to modify the input array. Sorting the array might change the input array. $\endgroup$ – saadtaame Feb 17 '16 at 23:58
  • $\begingroup$ @saadtaame, I can't understand your criticism. This answer does not involve modifying the input array. "If this is not the case, sort it." refers to sorting the sequence $b_1,\dots,b_{n+1}$, not sorting the original array. The very next sentence also makes clear that you keep track of the correspondence. I haven't tried to verify whether this answer is correct, but your criticism seems like a misunderstanding of the proposal. $\endgroup$ – D.W. Feb 18 '16 at 3:02
  • $\begingroup$ Rainer P, can you justify why this algorithm is correct in the case when the input array contains negative integers? I have to admit that I don't fully understand the problem, nor fully understand the proposed solution: what does "element count in between them" mean? If we have two pointers $b_s,b_t$ (after sorting), why are we guaranteed that $b_t-b_s$ corresponds to the sum of some range of $a$ (the sum of $a_i,a_{i+1},\dots,a_j$ for some $i,j$)? It might be the negative of that sum rather than that sum itself, if the order of $b_s,b_t$ got swapped during sorting. $\endgroup$ – D.W. Feb 18 '16 at 3:07
  • $\begingroup$ @D.W. When $b_s$ and $b_t$ get swapped during sorting, $i$ will be larger than $j$. But $\int_a^b f(x)dx = \int_b^a -f(x)dx$, so the solution is correct. In fact, my algorithm will always give the solution where $f(x)$ is positive, with the range either ascending or descending. $\endgroup$ – Rainer P. Feb 18 '16 at 8:23
  • 1
    $\begingroup$ @D.W. If the prefix sum array is already sorted, the two-pointers technique solves the problem in O(n) time and this part is correct. If it's not sorted, sorting it will ruin the indices in the array (we are looking for contiguous sub-sequences). How do you make sure that the solution you find is contiguous ? And the solution you find might correspond to a rearranged input array (that's what I meant by modifying the input array). $\endgroup$ – saadtaame Feb 18 '16 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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