AlgoDaily 21: Contiguous Subarray Sum

https://algodaily.com/challenges/contiguous-subarray-sum

There’s a fairly obvious brute-force O(n^2) way to do this by looping through every possible sub-array:

function sum(numbers) {
        return numbers.reduce((sum, x) => sum + x, 0);
}

function* allSubArrays(numbers) {
        for (let i = 0; i <= numbers.length; i++) {
                for (let j = 0; j <= numbers.length; j++) {
                        const slice = numbers.slice(i, j);
                        if (slice.length > 0) {
                                yield slice;
                        }
                }
        }
}

function subarraySum(numbers, targetSum) {
        for (let sub of allSubArrays(numbers)) {
                if (sum(sub) === targetSum) {
                        return true;
                }
        }
        return false;
}

This is O(n^2), so not great, but I can’t think of a different way to do it. We could make some small optimisations by skipping a subarray as soon as possible, but the worst case would still be O(n^2).

Algo Daily has a more efficient solution using a hashmap to cache previously calculated subarray sums. If we reach a point where the sum minus the target sum is in the sums cache, we know that it’s possible to make the target sum using a subarray of the numbers.

function subarraySum(numbers, targetSum) {
        const seenSums = { 0: true };
        let cumulativeSum = 0;
        for (let num of numbers) {
                cumulativeSum += num;
                if (seenSums[cumulativeSum - targetSum]) {
                        return true;
                }
                seenSums[cumulativeSum] = true;
        }
        return false;
}

This might be easier to understand with more extreme numbers as the example (often a good trick):

subarraySum([100, 3, 4], 7);

When we reach the final iteration, the seen sums are {"0":true,"100":true,"103":true} and the cumulative sum is 103 + 4 = 107.

We check if 107 - 7 = 100 appears in the seen sums, because we can exclude any irrelevant earlier sums by subtracting the target sum from the whole running total. As 107 - 7 = 100 does indeed appear in the seen sums, we know that we can achieve the target sum with the other numbers.


Tech mentioned