Subarray Sum Equals K (Javascript)

Watch someone try to solve the Subarray Sum Equals K problem in Javascript with a Microsoft engineer. Explore this problem and more in the world's largest library of interview replays.

Interview Summary

Problem type

Subarray sum equals K

Interview question

Given an array and a target, return the total number of continuous subarrays whose sum equals to the target.

Interview Feedback

Feedback about Winter Squirrel (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

3/4

What about their communication ability?

4/4

He did not right away go into solving the problem, he discussed the brute force initially and then worked through the optimal solution. He was good in taking hints and working through it. I would definitely pass him for the phone interview and love to have him as a collegue.

Feedback about Magnetic Rainbow (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

4/4

How good were the questions?

1/4

How helpful was your interviewer in guiding you to the solution(s)?

4/4

I like that I have never seen this question (or variants) before. This let me have practice with an interview in which I struggle a bit. The only note I have is that other interviewers had me step through my code with examples in order to catch bugs or incorrect code. I've noticed that you told me right away as soon as I wrote something incorrect. I'm not sure if one method is better than the other, but it's something different that I noticed.

Interview Transcript

Magnetic Rainbow: So which language are you familiar with?

Winter Squirrel: JavaScript.

Magnetic Rainbow: Okay. Sure. We can dive into the question if you're fine with it?

Winter Squirrel: Yeah, sure.

Magnetic Rainbow: Okay. I'm copying the question here. So basically, you're given an input array, and an integer k. So basically, you need to find out how many number of sub arrays in the contiguous positions in an array that sums up to that given value, k.

Winter Squirrel: Okay, I'm just going to be quiet for a second while I read this. Okay. So, I'm just going to write down some assumptions, and then you let me know if they're okay. So I assume that if the input array is empty, then we're just going to return zero.

Magnetic Rainbow: Yep.

Winter Squirrel: Okay. And if we don't find any, then we also return zero.

Magnetic Rainbow: Yep.

Winter Squirrel: Okay. Um, so I'm just, I'm going to say out loud, what I think a brute force solution here is, and then I think we could do better. So after I say it, please let me know if you'd like me to code it up, or go move on to the better solution.

Magnetic Rainbow: Sure

Winter Squirrel: So since we need to find sub arrays, the brute force solution is going to be if we do a nested for loop that lets us check literally every single possible sub array in this problem. So in this example, here, you would start at one, and you would check does one equal to two... no. Then you would check one one, that does equal to two, so you increment some sort of counter by one, and then you check 111, that's three. So that doesn't count. Then you move on to starting from next element, which is one that doesn't equal to two. So then you do one, one, that does equal to two increment the counter and then finally you go to one, which isn't equal. So that's the brute force solution. And in terms of running time, that's going to be an O(n^2) solution, where n is the length of the array.

Magnetic Rainbow: Right.

Winter Squirrel: And then the space would be just constant, since the only thing we need to keep track of is the amount of continuous separates that we've seen. So would you like me to code that up? Or should I move on to trying to find a better solution?

Magnetic Rainbow: Yeah, I think we can do better. Let's think about like maybe like take five or 10 minutes, think of like a better solution. If not, I could help you by giving some hints.

Winter Squirrel: Right. Okay, so since we're finding continuous sub arrays, my gut is currently telling me that we should maybe try out some sort of sliding window approach. So, let's do a sliding window here. Let's do an example. As we just did 111. I would imagine that we start off with, actually, I'm going to change this around a little bit so that it's clear what we're doing. Yeah, and in this case, let's do k is equal to five.

Magnetic Rainbow: Okay.

Winter Squirrel: By the way, I don't think this makes much of a difference, but are the numbers inside the array unique or no?

Magnetic Rainbow: No. They can have duplicates as well.

Winter Squirrel: Okay, that's fine. And one more question. If, say, for example, we have 1 2 3 1 2 3 as our array, and k is equal to six. Would both... can the continuous arrays be duplicates? So in this case, you have 123, which is a match, and then you have another 123. Would that count as two?

Magnetic Rainbow: Yeah, those count as two.

Winter Squirrel: Okay, cool. So then let's go back to our sliding window. Okay. So we would start off with the number one, which, and we'd also keep track of a sum variable. So we'd have the number one that is not equal to k. So we need to expand our window, then our window becomes one, two. And now our sum is three. That still isn't it. So we expand our window. Now our sum is going to be six. Now, since this... okay, another question... Can we have negative values?

Magnetic Rainbow: Yes. Okay. So I like your approach, like sliding windows, like you're thinking in the way like, whenever the sum is greater, you could probably like remove the elements from the, from the head. But they could also be like a negative number next, which would actually decrease the total sum.

Winter Squirrel: Right. Yeah. So let me think if that completely disqualifies the sliding window or not? Let me think.

Magnetic Rainbow: Yeah, so yeah, I think the the sliding window approach looks good to me. But you should somehow... do you know something about the prefix sums?

Winter Squirrel: About what?

Magnetic Rainbow: Prefix sums.

Winter Squirrel: Did you say prefix sum?

Magnetic Rainbow: Yeah.

Winter Squirrel: No, I think this is the first time I heard about it.

Magnetic Rainbow: Okay. Yeah, just try to think in this approach. Let's say like every index, you probably want to add the current value to the previous value. Previous in the sense that it's a previous index. Yeah. Try to come up... Try to see if using that technique, maybe you could see if you can come up with a solution, like take one simple example. Let use the 123 and k is equal to five. See if that can be... can you find like any solution or is it... Can you come up with like a solution from that approach? If not, I can help you.

Winter Squirrel: Can you just one more time describe the prefix, sum.

Magnetic Rainbow: So yes, sliding window. Okay. I'll just take this as the line number 62. For example, let's say we have one, two and three. So at index zero, I mean, these are the indexes. So at zero, the sum will be one. And the one index, the sum will be two plus one, the previous could be three. And the second index, the sum could be three plus the previous sometimes it could be six, right? And this index will be, let's say, just starting somewhere around zero, one, and two. So and we have the case k's value is five, right? Let's see this six and this five. If you'd subtract that value, you get one. Do you see any relation with this one here and that subtract value there?

Winter Squirrel: Okay, um, let me think about it.

Magnetic Rainbow: Sure. We can try one more simple example if you want, or you can use this. This one is good example actually. Yeah.

Winter Squirrel: Okay. Just in case, I'm going to write out also the original example, which is 1 1 1. And so that would map then to 1 2 3. And so let me just copy this line here, which is, and so what was our K in the original? It was two. Okay. And so. So the difference between this last element here, and two is also one. And just like in our example, above, so what is our relationship, then with the first number? I mean, they're the same. So now I'm wondering if, if the map to value at any index, if difference with K, if any previous map value is the same? Does that mean that we've found a continuous sub array?

Magnetic Rainbow: Yeah, from that next index to the current index, the sum is basically like what you're looking for, right? Yeah, you can take another example to try out some examples, if that makes sense. And see how you can come up with a solution. And probably take like a bigger example, maybe like four or five indexes or so that you'll be clear.

Winter Squirrel: So anyway, let's do 1 2 3 or let's throw in a negative number maybe. And three. And it could be unordered. So zero and five.

Magnetic Rainbow: Yeah. You missed the three over there. Probably. Just.

Winter Squirrel: Oh, yeah, you're right. Okay, what should we make our sum? Let's make our sum. Let's see... Let's do zero. Okay. So, our mapping then is 1 3 0 1 0 5. Okay. Okay, so in this case, then, our... the two sub arrays here that are continuous and the right answer are one, two, negative three, and one, two, negative three, zero, which conveniently enough in our map values show up as the same sum which would make me think that so long as our map value equals k, that's the right answer, but I'm now thinking about how to handle the situation right here, because the zero on its own is also a subarray. But, this entire mapped value here is based on starting from the first index. So let me think what can we do about that? Because if I start making, you know, this kind of array for every single element, that's not going to be any better than the brute force solution. So let me see if there's some other insight that I'm missing.

Magnetic Rainbow: Maybe think like suppose at the, let's say you have a final space for this array. And at every index, you try to compute this cumulative from the previous value. So you're computing that array only once for every index, and not...

Winter Squirrel: Okay, okay. So one thing that I guess we could do, is, I'm going to try to actually, like do this example from scratch. So like, we start at one. And so there's only one element, so we do one and one is not equal to zero. So let's say then that we keep going. So, then we add two.

Magnetic Rainbow: And also you should probably as mentioned by you, like, you were also trying to do some difference right from difference of this some minus that K. And see if that if you have seen already that prefix sum before. We should do that for every index, right?

Winter Squirrel: So we also keep track of the difference with k. Okay, let's see what that would give us. So the difference with k. In this case, it would just be the same number. Now, then my question is the difference with the specific number or the current sums? Okay, so then we're going on to the third number, which now we have zero, and then the difference between negative three and k is negative three. Okay, so now... let me think... now that we've come across the value that is k, should we do anything with this array? Let me think. I don't see... I'm just gonna keep going and see where this takes us. So then, once again have zero and then here we have zero. And then we have five, and then we have five. What relation does this have with K other than being the difference, but how does that help me?

Magnetic Rainbow: Okay, so let me help you with a simple example. So let's say you can try it out next with a negative number. So it might be like one, one and one, right? This is simple, right? Okay. And these indexes are, let's say, zero, one and two, and K is two. Okay, now, let's say the cumulative sum and let's say this is some kind of a map that I'm keep tracking of. So the cumulative sum is one at this index, right? And the difference basically is minus one here, one minus two is minus one. So we'll check in our map if you have seen this value. No, we haven't seen it. So let's store this current sum in our map, let's say one. And this counts... Okay, let's say only 1 is not already found in the map. So we stored that one in our map. And next comes is the prefix sum that is two now. And two is equal to our two, right? So we'll bump up our answer as one. Right here it was zero, we bump it, and we will do a difference as well. Two minus two, zero, we have the same two minus two, zero in our map, no, so we'll just add it to map. And the next accumulator is three, right? So three is equal to k? No, it's not. So what we do is we subtract the prefix sum three and from two, one. Have we seen it in our map? Yes, we did see one in our map. So what is this one in our map say that means? It was previously at some point the cumulative sum became one that means from that point indexed to the current value, the summary sum equals our value.

Winter Squirrel: Can you repeat that very last part, that at some point?

Magnetic Rainbow: So, the difference basically, what we do is we do this is equal to prefix sum whatever we have subtracted, minus k value. And if diff is already seen earlier, that means the indexes after that until now forms our sum value equal to k. Did you get this point? Or I can show you?

Winter Squirrel: Yeah, just let me think about this part right here, specifically. So we saw one, and then... Okay, so let me know if I'm understanding this correctly. Since we have already seen this one here, that means that between the point that we saw it up until now, there was a continuous subarray that added up to k.

Magnetic Rainbow: Yep, that's right.

Winter Squirrel: Okay. Interesting.

Magnetic Rainbow: So you can think about that example and see if you understood, otherwise we can stay. I'll go over it again.

Winter Squirrel: Okay, so let's try. What did we have? I think this one was a nice...

Magnetic Rainbow: Yeah. This is definitely good to understood.

Winter Squirrel: Okay. So let me redo this. So the difference between our current sum and k, I mean, it's going to be the same. It's going to be the same, is going to be the same. But now, we've already seen that zero. So that means which index is this?

Magnetic Rainbow: This is after reading index two, right? Yeah, from that. So after that two, yeah.

Winter Squirrel: Right. So I'm just gonna write down the indexes. And, yeah, so we saw the one at index zero, we saw the three at index one, we saw the zero at index two. And then at index three, we realized that we already have seen zero at index two. So the relationship, let's see what the relationship between index two and three is. So two would be negative three, and then three would be zero. Since negative three and zero don't add up to zero, let's see what happens when we take the first number exclusively. So that would be just as zero on its own, which does add up to k, which is the number, a continuous sub array that we're looking for. I'm just going to try out one more example. Okay, let's see, we have 0 1 2. Those are the indexes. Oh, wait, we already did this one. Let's do this. So 0 1 2 1 2 3. Good. We have 1 3 6. Okay, so the difference between five and one is four. Also just double checking, I noticed that in one of your examples, the difference is always the absolute value. So we're always dealing with positive numbers.

Magnetic Rainbow: It does not have to be, there might be cases where you can also encounter like negative values. If all elements in that are negatives, and we're also looking for a negative k, then we're dealing with negatives. But for simplicity for understanding, we can work off with the positive numbers, and then we can extend that. I mean that that works with negative values also, this concept, so.

Winter Squirrel: Okay, so five minus one is four, five minus three is two, and then five minus six is two, negative one. So we haven't seen any of the numbers previously, and there is only one answer in this question. Okay, so let's try adding another index. Let's do four...

Magnetic Rainbow: Actually, in the previous example, the minus one, probably you should do like, I mean, not absolute value, you should subtract from the prefix sum minus the k value.

Winter Squirrel: Okay. So in that case, it would be one minus five, which would be negative four, three minus five, which is negative two, and then six minus five, which is one.

Magnetic Rainbow: Actually, you should in the map, you're storing the the prefix sums, but you're taking the map against the diff, right? So okay, let me go over this example. So initially, the prefix sum is one. And diff is minus four, but the diff doesn't exist. So you add this sum to the map. And then the prefix sum is three. And you do three minus five, minus two, it's not in the map. Okay, that's fine. So you add this three to the map. The cumulative sum is six and you do six minus five, which is one, oh, we encountered this one in our prefix map. But you also add this sum to the map. So basically, you're keeping track of like prefix sums in the map. You're searching for the difference in the map. So that gives you if there is any continuous prefix sum with this diff value already existing.

Winter Squirrel: Okay, let me try this one more time, then. I think I'm starting to get it. So one minus five is negative four. We haven't seen negative four before. So we add one.

Magnetic Rainbow: I think that action part comes afterwards, because if you add it before, you could see that value again. I mean, that's, you can add that to the map after checking whether the diff exists or not.

Winter Squirrel: After taking the what?

Magnetic Rainbow: First, check the map for the difference. And then add the diff.

Winter Squirrel: Okay, right. So the difference is negative four, which we don't have in the map, so then we add one. Okay, so now, the difference between three and five is negative two, which we don't see in here. So we add three, and then the difference between six and five is one, which we have seen already. And so we increment our counter, so our sub arrays is equal to one. Okay, so then, let me once again do a more complicated example.

Magnetic Rainbow: Yes, but you should add to the map always, for the six case you found it. But there might be another big elements, which are looking for the six as the answer. So yeah, you should add six. There is another... Because let's say there is another five element here. If you did not add the six in our map, the next value will be 11 and 11 minus five is six, you search against the map for the six value, it doesn't exist if you didn't add to the map previously.

Winter Squirrel: Right. Okay. So this map is essentially keeping track of like, restarting the array, or the sub array somewhere in between. Okay,

Magnetic Rainbow: Yeah, the map is storing all the prefixes.

Winter Squirrel: Okay. So then let me run through this one more time, then. Okay, we have the number one. Let me get k, what was k in this example, I think it was zero. So the difference between one and k is just one. That's not here yet. So we stick the number one in. The difference between... or yeah, the difference between three and zero is three, we have not seen three yet. So we store three. The difference between zero and zero is zero. We haven't seen that yet. So we add it. Now I'm debating whether we should increment the counter yet, I'm going to hold off until I finish this example. So zero, and then we have another zero here, and that does exist in our map. So we increment our counter once, let's say count is equal to one, and then we don't add zero, since we've already have a zero in here. Then we get to five, five minus zero is five, that doesn't exist here. So now we have a five. Now the problem with what I just did is that there are three answers here. But I managed to only increase my count by one. So that tells me that we not only need to increment when we find a match, but also when our sum adds up to k. Because in that case, yeah. Okay. Yeah, yeah.

Magnetic Rainbow: And also, then, you're right in both cases. When you find a match, you should increment it, when the prefix sum is equal to k, you should increment it. But there's one small case where... so whenever you find a match, it could happen that here, in this case, the map already has a zero. In this case, it's better you store the number of times we have seen this prefix sum, because what I'm saying is, let's say and I'll tell you an example here, let's say one, two, and minus three, there is a zero, and then there is a one to minus three, right? Here in this case, and k is equal to two here... k equals zero here. So, by the time you reach here, at the end of that array, so initially, you store one, then store three, this is a count of how many times you have seen this. And zero, you see only the one time. This index, basically the index two, this is what the whole map looks like. And after the index four, the count should become two. Because at this point at the end, you're searching for zero, we have seen zero prefixes two times. I mean the difference. So you should basically, when you're adding, when you found a match from the map, you should add how many prefixes of that match basically, how many times you have seen that? Because that's how many ways you can make the sub arrays with that prefix. Did you get that?

Winter Squirrel: Yeah, yeah, that makes sense. So our rules increment when we or our sum adds to k. And when we seen the prefix, and then we do this increment by num times seen.

Magnetic Rainbow: Yep, that's correct.

Winter Squirrel: Okay. Okay. I think that with all the zero examples. I think we're covering all edge cases. Let me just do one more quick example, which is all negatives. Let me find our original example. -1 -1 -1. Okay. Let's say k is equal to negative two. So our sum is negative one. We haven't seen negative one before. So we say, okay, negative one, once. So then we go to next one, and we have negative two. Negative two's a match. And so our count is set to one. And then we haven't seen negative two appear yet. So then we say negative two, one. So then we get to negative three. Yeah. And so the difference here is negative one. Also, sorry, the difference here was zero. Because negative two and negative...

Magnetic Rainbow: In the map you always keep the prefix sum, not diff.

Winter Squirrel: Right. My bad. So negative three, the difference here is negative one, which we have seen before one time, so then our count becomes two. And that means the two subarrays are this. And this.

Magnetic Rainbow: Yeah, you have to add the minus three into the map.

Winter Squirrel: Right. Sorry. So then we do negative three, which we've seen once. And yeah, so I think we're covering all the cases here. We've covered positive numbers, zero sum and negative numbers. Should I get started on coding?

Magnetic Rainbow: Yeah, yeah. Yeah. I think yeah, we'll stop at like maybe 12:55. That's okay. Okay, so in, like, yes, 17 minutes. Yeah, okay. Let's see where's JavaScript? Okay, so function... I'm just going to call it prefix sums, I don't have a much better name. And we are taking in an array and k. So we're going to keep track of our matches, or rather, let's do sub arrays. We started off at zero and then return sub arrays. And then for... We also keep track. Actually, we don't even need to keep track. Let's keep track of sums, an array, and then we will keep track of actually... Yeah, this is just an object. So the first thing that we do is we say our... actually our current num is equal to array i and then diff with k is equal to current num minus k. Okay, so when we use...

Winter Squirrel: Is this the current number or is it the current sum until now?

Magnetic Rainbow: So let's take the current num and then we say that the sums at index i is equal to... okay, let me do a base case. After I write this out, I'm going to try to go through an example to make sure that there's no bugs. Okay, so our sums have increased. And so I'll just say that the current sum is equal to sums i. We check if that already exists in seen, so if diff in seen, then we we have a sub arrays plus plus and then we also have to say that otherwise... Actually, no, not yet.

Winter Squirrel: You add how many times you have seen it?

Magnetic Rainbow: Right. So plus equals diff with k. Okay, so that's... where are we now? Then we also have to check if current sum equals to k and then subarrays plus plus, and then we have to add the either add the current number, or increment it. I think we could increment it here. Wait, let me think about that. No, no, because this is the difference. This is the current value. Right. So let's do if current sum in scene... Yep. And then I think that's everything. Let me see. We incremented our sums. We checked our difference with k. If we've already seen it, then we increment by that many numbers. And then if we're matching the current k, then we're incrementing by one. And then if we've already seen the current sum, we increment it by one otherwise we set it to one. I think that covers everything because this for loop in the case that we have an empty array is going to...

Winter Squirrel: Yeah, I could add like a one simple optimization. Like what is the time complexity for this?

Magnetic Rainbow: Oh, yes. So the time complexity, we're only iterating through the array once and we're doing a constant amount of work inside of the loop. So the, let me write it out here... Time is O(n). And in terms of space, we need to keep track of our sums. And we need to keep track of a hashmap. The hash map, if all this sums are unique, that would mean that our hashmaps length is going to be O(n). And then the sums that we're keeping track of will always be O(n). So the space complexity is O(n). That being said, this won't be an asymptotic difference, but I don't think we actually have to keep track of an entire array for our sums, just the previous and current number.

Winter Squirrel: Yeah, that's what I want to like, tell you, I mean, you can eliminate this constant sum instead, then just use the current sum, just initially initialize this current sum as zero, just like sub arrays. And just increment that with plus plus like something like this. And then you can do... it should work. I mean, you can just tell eliminate all of the sums array.

Magnetic Rainbow: Yes. So the only difference is, current sum is going to be a let. And then right here, it would be like this. And then we don't need sums. So actually, we could do. We can do. Do we get rid of this? Yeah, I think we could get rid of this.

Winter Squirrel: Even the current num can also be removed, right? Yeah. We are not using the current num anywhere.

Magnetic Rainbow: Oh, yeah. You're right.

Winter Squirrel: So yeah, this should be good.

Magnetic Rainbow: Yeah. Okay. Yeah, so that's cleaner, but our space and time stays the same, though.

Winter Squirrel: Yeah, that's true. You can actually try this sum in leetcode. Are you familiar with leetcode?

Magnetic Rainbow: I am. So this is basically like problem 560. And there is another extension to this problem. I will probably, if you have time, I would have asked that. But there is another sum. Similarly, this basically, it's a call like a liquefy low, like what is the number of that? Which you can actually try it out later. Problem 437. So do submit this, and then submit the 560 and then submit the 437. So you'll be thorough with this prefix sum problems.

Winter Squirrel: Mm hmm. Yeah, this is, uh, this is definitely the first time I've even like seen this concept.

Magnetic Rainbow: Right, right. Yeah. Yeah, even I was asked this kind of question somebody asked before, so I thought of asking it here so that it helps the person. Overall you did good. Since you come up with solution, I mean, with the help of like, hints, I would actually pass if it was a phone, I would definitely pass you because you were able to code it up to the time. During the on sites. I might be like, it's not an official, but they would be like a half enough, because some of the interviewers thing that they should come up with the solution without the hints. But for the phone interview, you did pretty good.

Winter Squirrel: Okay. Yeah. So I have a question for you as an interviewer. Like, what... So if the candidate hasn't seen the, like, the type of problem before, right? And it isn't, like, reliant on some very general data structure, like it's not like the candidate doesn't know what an array is, is something closer to this? What is the expectation from the candidate in terms of like, how many hints would you say is a reasonable amount for the candidate to receive without being like docked points?

Magnetic Rainbow: Right. So like, you know, like in the hiring committees generally say like, what we write it is basically like, it's good if the interviewee, I mean, the guy who is taking the interview, like in your case, like I told you since you are not similar the prefix sums, I was able to like guide you in that approach. So the interview expectation is that if he gives hints to interview, the interview is basically trying to trying to take his ideas and coming up with a solution. That's what's expected. And for the number of hints, it's better if we try to minimize it to like three to four. So that gives an impression that like, at least the interviewee is working on the approach. Like I just let you go through over once, then you are coming up with examples. I mean, I feel like it's really good because you're taking the ideas and trying to come up with the solutions and your building upon top of that approach.

Winter Squirrel: Okay, um, and then I have one more question. Based off, like, stuff that I read online that interviewers look for. Is, um, would you personally prefer, like, let's say that I have seen this problem before? And at this point, I have it like, memorized. Would you as an interviewer, prefer seeing me just completely destroy the problem? Or would you rather that I kind of struggled through it a little bit? Because I've heard on online that interviewers preferred if I like, struggled through it a little bit more, because then they have more signals, like my problem solving abilities, versus oh, this candidate just memorized this problem.

Magnetic Rainbow: Yeah. Yeah. So basically, like generally the interviews will be able to know whether he has already seen this problem or not. So general idea, if you already know the problem, there are two approaches to take. Some people say like, just go ahead and tell them. The other approaches just say that you already have seen this problem and explain them the approach, it's up to the interviewer to decide whether to change the problem or to even like, continue with the same problem, because he might be thinking that okay, he already knows this concept. So let's try to finish this up fast and try to go like a much like a harder problem next. Just like if you are able to do it quickly, the #560, like this problem, I would have gone to problem 437 because you already know this. So then it's completely up to the interviewer. I would say like, I'm a guy to where, it's fine if you already know the question, but I would expect like a cleaner, better solution even though you know the solution. But as you said, yes. Because interviews wants to see like a little bit struggle so that it knows like whether this guy is like, trying harder to get to the solution. So that it generally gives like a good impression.

Winter Squirrel: Hmm. Okay. Did I have any other questions? Yeah, I think that's it.