Leetcode diary: 560. Subarray Sum Equals K

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

link

Was anxiously reading a leetcode post on this being in the phone interview. Thought of doing it and failed so might as well detail this whole thing out.

I liked this problem because it touched upon two things I am really bad at:
1.) prefix sum implication: this technique is really easy to understand how to do, but it's really hard to see how it can become helpful, especially intuitively.
2.) How to approach problems with array of integers. I don't really know how to describe this. Whenever I see a problem with array of integers on leetcode medium, they seen to be a category of crazy magic all by itself. It just feels so fucking bizarre to me.

The problem is that given an array of integers, find a continuous subsequence that sums up to a target value.

At first glance, this is a finding subsequence problem and just matching the sum of each sequence to the target value. However, as we all know too dang well, this is never the answer cause the performance will be too shitty. It is very rare exception that a question like this will accept brute force as answer.

Therefore, at this point you should think about what could possibly make this better. Whenever you are hit with an array of integers, there is almost always something about taking advantage of the fact that the type is integers (or numbers really).

This is when prefix sum can come into play. This is because given:
[A,B,C,D,E,F,G]

the prefix sum progression will be
[A, A+B, A+B+C, A+B+C+D, A+B+C+D+E. A+B+C+D+E+F, A+B+C+D+E+F+G]

This is where the magic is at. How do you use this combination of numbers ?
Usually when it is prefix sum, you'll have to utilize subtracting on prefix sum from another or subtract from the original array so that you can get the sum of subsequence. For example
To get B+C+D+E, instead of adding them individually in a for loop. When prefix sum, it is literally:
B+C+D+E = prefixSum(E) - A, for prefixSum(E) = A+B+C+D+E.

So how does that help us getting all of the possible subsequence sum? well let's by looking at

[A, A+B, A+B+C, A+B+C+D, A+B+C+D+E. A+B+C+D+E+F, A+B+C+D+E+F+G]
if we subtract by A for each we get:
[B, B+C, B+C+D, B+C+D+E. B+C+D+E+F, B+C+D+E+F+G]
this is all the combinations without only A, suppose we then subtract by A+B:
[C, C+D, C+D+E. C+D+E+F, C+D+E+F+G],
see the pattern yet ?
the answer is that since it has to continuous subsequence sum, what we are finding is just the sequence from any index plus the next, plus the next, plus all the way to the end of array. So all the sequences for B is: [B, B+C, B+C+D, B+C+D+E. B+C+D+E+F, B+C+D+E+F+G].

The prefix sum just makes it somewhat easy, but not really intuitive way to get it.

Here is the code below:

var subarraySum = function(nums, k) {
    const prefix = [];
    let answer = 0;
    let sum = 0;
    nums.forEach(function(num){
        sum+= num
        prefix.push(sum);
    });

    for (let start = 0; start < nums.length; start++) {
        for (let end=start; end < nums.length; end++ ) {
            sum = prefix[end] - (prefix[start-1] ? prefix[start-1] : 0);
            if (sum == k) {
                answer++;
            }
        }
    }

    return answer;
};

Amazingly this gets the correct answers ...except its performance is bad... :( fuck...

Note that the leetcode discussion mentioned that the prefix sum solution got the okay from the interviewer though, so just know that having absolutely the best solution may not be necessary to pass the interview.

Before we dive into the optimal, there is actually another much easier answer to this.

Notice that we just want:
[A, A+B, A+B+C, A+B+C+D, A+B+C+D+E. A+B+C+D+E+F, A+B+C+D+E+F+G]
[B, B+C, B+C+D, B+C+D+E. B+C+D+E+F, B+C+D+E+F+G]
[C, C+D, C+D+E. C+D+E+F, C+D+E+F+G]
If you really understood what is the goal of the question, you should realize that WE ACTUALLY DIDN'T NEED THAT PREFIX SUM BS!!!!

what we are doing is literally:
Starting from any index, loop to the end and accumulate the sum on the way and find out whether any of the sum matches the target.

This is why it's fucking important to really understand what the question actually needs to answer the question before diving in...sigh... I have a LONG WAY to go...

Below is the code via java... I think it's self-explanatory now and didn't want to force myself to translate it to js:

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int start = 0; start < nums.length; start++) {
            int sum=0;
            for (int end = start; end < nums.length; end++) {
                sum+=nums[end];
                if (sum == k)
                    count++;
            }
        }
        return count;
    }
}

(the above fails submission due to performance too btw...)

The optimal solution is kinda...insane ... it requires the prefix sum and a hashmap to make it work.
For example:

[A, A+B, A+B+C, A+B+C+D, A+B+C+D+E. A+B+C+D+E+F, A+B+C+D+E+F+G]
this is the prefix sum progression

we know that given the question requirement, target MUST BE A SUM OF SOME SEQUENCE.
Therefore, let's say the target equals C+D+E, what does this mean? This means that when we do
prefixSum - target = some other prefixSum too.
let's say:
target = C+D+E
A+B+C+D+E - C+D+E = A+B
Well, when do we get A+B ? well before A+B+C+D+E when we are running through for the prefix sum for loop. So what does this mean? It means that whenever we do (prefixSum-target), if the result already exists in the prefix sum, it means that the target must be some kind of sequence in the array. Therefore we could just do:

var subarraySum = function(nums, k) {

    let sum = 0;
    let answer = 0;
    const prefixMap = {0:1}

    nums.forEach(function(num){
        sum+= num;
        const key = sum-k;
        if(prefixMap[key]) {
            answer += prefixMap[key];
        }

        prefixMap[sum] ?
            prefixMap[sum]++ : 
            prefixMap[sum]=1;
    });

    return answer;
};

the {0:1} base case is important as 0 means that prefixSum-k = 0, so prefixSum = k.
Another caveat that makes this solution difficult is that because of negative values, it means that we could potentially have same prefix sum in the array, such as one that goes [... 1, -1 ...].

This one is actually insane, I learned a lot from doing this question, hopefully you learned a thing or two from reading my long ass article.

Let me know anything on your mind after reading through this, THANKS!

Comments

[Osama Ayman]

Thanks Kevin for sharing the whole thought process!
It's really helpful to see the challenges encountered in each part of this questions and the way to think to tackle them.