3
$\begingroup$

Given an array of N non-negative integers, and a number K, we need to find two non-overlapping contiguous subarrays that have a total sum of K. Our algorithm is supposed to find the minimum total length of the two subarrays that have total sum K.

Also, after I checked the biggest test cases that we got, N doesn't go above $10^4$ and K doesn't go above $10^6$ (but specific subarrays can have a sum way larger than that)

The algorithm implementation (using C++), must have a time complexity of at most O(logN * N^2).

The only idea I've had that is better than O(n^3) is to find all possible contiguous subarrays and their sum (O(N^2) using a prefix sum array), then sort them by sum (O(logN * N^2)), and for each subarray I do a binary search to find the subarray that has the remaining sum (which is K - (sum of first subarray)).

While this idea has better time complexity than O(n^3), its space complexity is pretty bad, because I have to save three arrays of size N(N+1)/2, and the C++ program ends up using 1-2 GB of RAM for large N (>1000).

So my question is: Is there any way to solve the problem efficiently, without the need of the longer arrays?? Or is there any other way I can implement the idea above with C++ so that I don't use up so much memory?

Thanks

$\endgroup$
4
  • $\begingroup$ I don't "see" the 3rd array to keep. Rather than starting to argue about a constant factor of, say, 6 here, I suggest asking for a review of your code on Code Review@SE - they even have a guide How to get the best value out of Code Review - Asking Questions. $\endgroup$
    – greybeard
    Commented Nov 25, 2021 at 8:18
  • $\begingroup$ It really makes no difference, since one single array of $10^8$ integers will be more than 64MB. The problem here isn't the implementation, but the asymptotic complexity, and trying not to store an array of size $O(n^2)$. I still haven't found an acceptable solution, but as I said, I will post the answer tonight probably, or tomorrow morning. $\endgroup$
    – NiXt
    Commented Nov 25, 2021 at 8:30
  • 2
    $\begingroup$ Somebody commented an entirely similar problem on SO is similar to this one. $\endgroup$
    – greybeard
    Commented Nov 29, 2021 at 17:55
  • $\begingroup$ Yep, I'm pretty sure we are from the same class :) Our prof said he will upload a $O(n^2)$ solution this week. I'll let you know when I have it. $\endgroup$
    – NiXt
    Commented Nov 29, 2021 at 21:29

5 Answers 5

1
$\begingroup$

The following algorithm works but does not achieve the required time complexity of $O(n^2 \log n)$, since I misread the time constraint as just being subcubic.

Let $a_i$ be the $i$-th element in the array and $\varepsilon > 0$ be an arbitrary small constant. Construct a prefix sum array (in time $O(n)$) and then, for each pair $i,j$ with $j-i \ge n^{1-\varepsilon}$ generate the tuple $(\sum_{h=i}^j a_h, i, j)$. This requires time $O(n^{1+\varepsilon})$.

Next, construct two sorted lists $L^+, L^-$ containing the above tuples. Both lists sort the tuples w.r.t. the first entry. Additionally, the first (resp. second) list breaks ties w.r.t. the second entry while the second list breaks ties w.r.t. the third entry. This requires time $O(n^{1+\varepsilon} \log n)$.

Next use your approach with a slight variation: guess the start position $i$ and the end position $j$ of the first subarray (there are $O(n^2)$ guesses). For each guess $(i,j)$:

  • Compute the sum $S = \sum_{h=i}^j a_h$ (in constant time).
  • Binary search $L^+$ and $L^-$ to decide whether there is a disjoint array of length at least $n^{1-\varepsilon}$ with sum $K - S$. If this is the case you are done.
  • Otherwise exhaustively search all disjoint subarrays of length smaller than $n^{1-\varepsilon}$.

Overall this requires time $O(\log n + n^{1-\varepsilon}) = O(n^{1-\varepsilon})$ per guess and time $O(n^{3-\varepsilon})$ in total, which falls within the time requirements. The space requirement is only $O(n^{1+\epsilon})$.

$\endgroup$
2
  • $\begingroup$ Thanks for the answer!! Do you happen to have any Wikipedia link or something similar where I can read about how/why this technique works?? I have never seen any algorithm that uses the same technique, so any extra info would definitely help. $\endgroup$
    – NiXt
    Commented Nov 21, 2021 at 15:49
  • 1
    $\begingroup$ I'm sorry I don't know if this technique even has a name. In general splitting the work into a "small parts" and "large parts" and using different approaches to handle each part is a quite common strategy. The actual details vary from problem to problem. Here we are getting a trade-off between time and space that depends on the threshold where we switch from exhaustive search to binary search. $\endgroup$
    – Steven
    Commented Nov 21, 2021 at 16:27
1
$\begingroup$

Compute the sums of all subarrays ($O(n^2)$), sort all distinct sums ($O(n^2\log n)$), then find all pairs of sums that sum to $K$ ($O(n^2)$).

Note each sum may correspond to multiple subarrays. Given two sums that sum to $K$, you have to check for all pairs of subarrays corresponding to the two sums whether they overlap. To solve this, for each sum, pre-find the subarray with the leftmost end position and the subarray with the rightmost start position. You only need to store and check these two subarrays (also note to store a subarray, you only need to store its start position and end position).

$\endgroup$
5
  • $\begingroup$ start position and end position for the checks, it should do nicely to just know the end of the leftmost and the start of the rightmost subarray. The other end can be re-established once a pair is found. $\endgroup$
    – greybeard
    Commented Nov 24, 2021 at 2:26
  • $\begingroup$ This is exactly the algorithm described in the third paragraph of the question. As the question states, this has running time $O(n^2 \log n)$ and requires space $O(n^2)$. The question asks whether it is possible to achieve the same running time with lower space complexity. As such, I don't see how this answers the question that was asked. $\endgroup$
    – D.W.
    Commented Nov 24, 2021 at 17:39
  • $\begingroup$ exactly the algorithm described in the 3rd paragraph of the question with notable details such as keeping no more than two positions for each sum. There have been two characterisations of the storage requirement: 1) three arrays of size N(N+1)/2 2) 1-2 GB. While details may not improve asymptotic growth, they may or may not alleviate a problem in one/any use case. $\endgroup$
    – greybeard
    Commented Nov 24, 2021 at 18:36
  • 1
    $\begingroup$ I tried storing only the distinct sums, but it still doesn't save much space (we can only use 64 MB as temporary storage while the program is running, so I think that any solution that stores information about all the subarrays is out of the question). Anyhow, in a couple of days we will learn the solution, and I will let you guys know. $\endgroup$
    – NiXt
    Commented Nov 24, 2021 at 19:02
  • $\begingroup$ leftmost end position [and] rightmost start position would have done if the original question asked for any pair. Alas, it asked for minimum total length. $\endgroup$
    – greybeard
    Commented Nov 25, 2021 at 5:47
1
$\begingroup$

Our professor gave us this solution, which has $O(N^2 + K)$ time complexity, and $O(N+K)$ space complexity (since for the biggest test cases $K$ is about $N^{1.5}$, it is as good as $O(N^2)$ for these upper bounds).

We start by initializing an array $Lengths$ of size $K$, every value set to $N+1$, and calculating a prefix-sum for the initial array. We also keep a variable $min$ for the final answer (initially set to $N+1$).

Then we iterate the initial array with an index $y$, starting from $N-1$ down to $0$. For each iteration we do the following:

  1. We iterate the array with an index $z$ starting from $y+1$ up to $N$. For each subarray, we calculate its sum, and if its length is less than $Lengths[sum]$ (where sum is the one we just computed), we set $Lengths[sum]$ to $z-y$, the length of this subarray.
  2. We iterate the array with an index $x$ starting from $0$ up to $y$. For each subarray, we calculate its sum, and if this subarray's length PLUS $Lengths[K-sum]$ is less than $min$, then we update $min$ with the new value.
$\endgroup$
0
$\begingroup$

The restriction to non-negative values simplifies solving the problem drastically:
Once the sum has reached $K$, adding elements increases length, if not sum.

This reduces the number of subarrays to know from $O(n^2)$ (start and end) to $O(K^2)$ (length and subtotal).

If $K$ is not greater than zero, you dont even need to inspect the array.
Check if $K$ is the value of an element of the array upfront: With $0 < K$, the combined length won't go below 1.

With a largish K and hell bent going lowest/$o(n^2)$ space, how about the following?

  1. let $array$ be the input array of $n$ integral numbers no less than 0;
    $best$, $left$ and $combined$ for the best pair known
    the subtotal of the left subarray, its length and the combined length;
    $length$ and $end$ arrays of $n$ candidate subarray lengths and ends, respectively
  2. for $target$ from 0 to $K-1$
    1.1. from index 0 up, for each subarray totaling $target$ of record brevity, keep length and end
    1.2. next $target$ if none found
    1.3. for each subarray $right$ with sum $K - target$ from the end of $array$
           if sum of its length and the shortest one kept "to the left of $right$" $^*$
           bests $best$, update $best$
  3. re-find the rightmost subarray with sum $K - best$ and length $combined - left$

$O(n)$ storage, $O(nK)$ time: $O(n^2 \log n)$ where $K \in O(n \log n)$

Exchange the roles of subarray length and and target subtotal for
$O(K)$ storage, $O(n^2)$ time

$^*$ linear search from the end should do nicely, if the last index used is kept

$\endgroup$
5
  • $\begingroup$ I'd try to start from both ends: before meeting in the middle, there can be no overlap. $\endgroup$
    – greybeard
    Commented Nov 25, 2021 at 6:04
  • $\begingroup$ Generally, my experience with algorithms that depended on K (e.g. O(n*K)) is that they are really slow, so I guess that K can get a few orders bigger than n. Unless I manage to put it in as a logK (some kind of binary search I suppose, but I haven't worked the details) it won't help. $\endgroup$
    – NiXt
    Commented Nov 25, 2021 at 7:26
  • $\begingroup$ You disclosed a lower limit for $n/N$ - can you add an upper limit and limits for $K$, in the question? $\endgroup$
    – greybeard
    Commented Nov 25, 2021 at 7:30
  • 1
    $\begingroup$ I have derived that from a bunch of test cases that we got, but I'll check the biggest ones, and update the question. $\endgroup$
    – NiXt
    Commented Nov 25, 2021 at 7:32
  • $\begingroup$ @greybeard Could you elaborate a bit on the exchanging of roles of "subbaray length" & "target subtotal" ? If you mean that we are initially fixing the left subarray length to L, for $1\leq L \leq n-1$, I don't see how we could "check" the candidate right subbarays in $O(n)$, for each L, (i.e. $O(n^2)$ for the total algorithm). Could you explain that part? $\endgroup$
    – entechnic
    Commented Nov 29, 2021 at 15:44
0
$\begingroup$

Slight modification to other answers that may help:

  1. Since one subarray must have a sum from 0 to K/2, and the other must have a sum from K/2 to K, only look at subarrays with a sum <= K. This may help a lot, especially if K is much smaller than the total size of all array elements.

  2. If K is large, but heuristically you expect only few solutions, pick a prime p and find solutions modulo p, picking p large enough so there are still few solutions, but small enough to reduce your memory requirements. Then check whether your solution modulo p is a solution of the original problem.

  3. Once you found a solution with length M, only consider subarrays with fewer than M elements.

$\endgroup$
0

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.