For me, the C++ clutters an otherwise interesting problem. The basic algorithm is simple, but the edge cases (starting indexes / starting sum value, the literal array endpoints, keeping the lower dynamic endpoint <= upper one, no solution found) make it non-trivial to implement cleanly. This is my best effort in JS:
function sum(target, arr) {
let [a, b, cur] = [0, 0, arr[0]]
while (cur != target && b < arr.length) {
if (cur < target || a == b) {
b += 1
cur += arr[b]
}
else {
cur -= arr[a]
a += 1
}
}
if (cur != target) return null
return [a, b]
}
Given an unsorted array (sequence) of non-negative integers, find a continuous sub-array (sub-sequence) which adds to a given number S. Implement the solution as a generic algorithm, but visualize the results with indices that are 1-based.
Despite the fact that I don’t like those artificial interview questions, I was curious to see how my naîve solution would look like. I was using a sum variable inside the outer loop, which results in an O(N^2) algorithm: Go.
This version isn’t very useful for the final solution that will be presented below, but allows us to calculate the complexity of this solution, O(N3), as we have 3 nested loops (with N being the number of elements in the sequence)
Where is the third inner loop, is it the call to std::accumulate(?
The loops are nested, so it’s not O(N). That said, I only see two nested loops, and the naive solution is to test every possible pair of endpoints, which is nC2, which is O(N^2).
For me, the C++ clutters an otherwise interesting problem. The basic algorithm is simple, but the edge cases (starting indexes / starting sum value, the literal array endpoints, keeping the lower dynamic endpoint <= upper one, no solution found) make it non-trivial to implement cleanly. This is my best effort in JS:
Try it online!
Another variation is to find the shortest such contiguous sub-sequence.
Despite the fact that I don’t like those artificial interview questions, I was curious to see how my naîve solution would look like. I was using a sum variable inside the outer loop, which results in an O(N^2) algorithm: Go.
Where is the third inner loop, is it the call to
std::accumulate(?I don’t understand singpolyma’s reply, so I might be missing something, but yes
std::accumulatehas linear time complexity.… I think they mean
N3also known asO(N)…The loops are nested, so it’s not O(N). That said, I only see two nested loops, and the naive solution is to test every possible pair of endpoints, which is nC2, which is O(N^2).
I wasn’t doing analysis, only commenting that
O(N3)would be nonsense. If they meanO(N^3)that’s fine of course.You can tell it’s a copypaste error because nobody would write N3 to mean N×3, they’d write 3N.
That’s just how it looks in the cut and paste. In the article the 3 is super-scripted.