LeetCode Subarray Sum Equals K Solution Explained - Java

Preparing For Your Coding Interviews? Use These Resources
————————————————————

Other Social Media
----------------------------------------------

Show Support
------------------------------------------------------------------------------

#coding #programming #softwareengineering

[prek]

I understand you are trying to solve the questions for everyone. But it feels it has become a chore for you and you are not involved in explaining the crux of the solution and are more concentrated on just spitting out the solution. There is a solution section in leetcode. People come to watch videos because they couldn't understand the solution on a granular level.

[alammahtab]

Here is the approach : ( you might find it helpful)

Say you are given an array e.g. [a0, a1, a2, a3, a4, a5, a6... an] .

[a0, a1, a2, a3, a4, a5, a6, ... an]
^ ^
sumI sumJ


sumI = sum of numbers till a2 (a0 + a1 + a2)
sumJ = sum of numbers till a5 (a0 + a1 + a2 + a3 + a4 + a5)


Now lets say the difference between sumJ and sumI is equal to k.
What that means is, the sum of numbers between a2 and a5 is equal to k ( a3 + a4 + a5 = k ), which means we found a subarray whose sum is equal to k.

We can write a3 + a4 + a5 = k as sumJ - sumI = k and sumJ - sumI = k can be written as sumJ - k = sumI

The expression sumJ - k = sumI, means have we already seen a sum which is equal to sum at current index j minus k. If yes, it means we found a subarray whose sum is equal to k.

And we keep track of how many times we see a particular sum using a HashMap.


Code :
class Solution {
public int subarraySum(int[] nums, int k) {
if(nums == null || nums.length == 0)
return 0;
int count = 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int sum = 0;
for(int i = 0; i < nums.length; i++) {
sum += nums[i];
if(map.containsKey(sum - k))
count += map.get(sum-k);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
}

[suhasnayak]

This is just my suggestion: @2:50 You were finding it hard to explain, i know it's hard to explain it orally. Why don't you use white board and explain your approach first and then start with coding ? That way it would be lot easier to understand the problem as well.

[andrewxie]

i feel like he's just reading the leetcode discussion

[javanrajpopat]

"I think I have explained it pretty well!" No, you didn't.

[hemantv]

count=0, b=0;
K=sum to find in subarray
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)
{
b+=a[j];
if(b==k)
count++;
}
b=0;
}
printf("%d", count);

This might work for above problem with O(n^2) complexity

[sase]

We need to realize it requires reverse thinking, the goal is to find how many times/counts that sum of subarrays = k, we put all continuedly sum[i] in the map, for example, when we check 5th position in the map, we find value at (sum[5] - k) = sum[2] in the map(reverse logic), that means nums[2] + nums[3] + nums[3]+ nums[5] = k (normal logic). it means we found 1 count, repeat same process to find final counts.

[riyadshauk]

Given how concise you were, your video was useful for me up to 5 minutes in. After you had explained the idea that the sub-array can contain negative elements, as you were talking about why the hash table should contain key-value pairs of type (Integer, Integer). A little bit of thought on the viewer's end (an informal proof intuition) on what that means, did the job for me. Then the Leetcode solution made sense, a lot like Two Sum, which you also alluded to earlier in the video.

The idea for why we need to store the number of occurrences of some number seen in the cumulative sum (rather than just a boolean value): The cumulative sum can only ever equal a number that it's already equaled if there exists a negative sum, followed by a large enough positive sum; furthermore, if this is the case, then we choose any subarray in the region (which we didn't store indices for, unlike Two Sum), s.t. the sum, for any iteration i, is equal to sum_i - k. Since we can choose any of those occurrences, the maximum number of sums, for some iteration i, that equal k would be {hash table}.get(sum_i - k). We simply accumulate this sum in a result variable as we're looping through the array, all in one pass. This problem is a nice extension of the ideas of Two Sum, but the main implementation difference is, instead of storing indices, we store a number of occurrences (understanding why/how is the whole interesting part of this problem and why people stumbled upon this video, in particular, in the first place).

[ujjvalsharma]

Hey Nick your videos are amazing, and you are doing a great job. However, I feel that you can improve in your videos by explaining on a white board about an algorithm. For instance, step by step explanation and why one should use that algorithm.

[mandy]

Awesome explanation. At around the three minute mark I almost punched myself thinking "how the heck did I not think of this approach". soo close. Need to keep grinding. Thanks for the video! I do agree with the other viewers that a visual would have been great. Only reason I got this one quick is because I had spent like an hour thinking about it before I came to this vid.

[pvchio]

I can just go to leetcode and see the solution.. dude if you don’t know how to solve the problem, just don’t make a video... it’s funny at the end you said you explained it pretty well but you were literally reading the solution smh

[khakr]

Explaining is not typing or fixing compilation errors. Anyone can do it. The solution to this problem lies in line number 13 and you just skipped it.

[alexhong]

the basic idea is, say sub sum is (i, j) and i < j, then we knew sum(0, j) - sum(0, i) = sum(i, j) which is k. now, sum += num[i], and we wanna know how many sum - k that we have. i.e: ___i__j__ k is between i and j. hope is helps

[jorgegonzaloalfaro]

I feel horrible when these walkthrough guys say, "it's not that hard, or it's easy". i'm over an 1 hour in trying to understand the solution and i still don't get it :(, BUT hey, thanks for the video man!! just gotta keep grindinn these leets

[anubhavc]

Saying it's pretty obvious does not help in understanding the concept :)

[joshjuret]

Saying "it's clear", "it's pretty obvious" does not really help to explain things, I like your videos overall and you are doing a great job, but I wanted to point that out and hopefully, you can do better.

[ayushnishad]

Hey Nick, can you explain subarray with the sum not equal 0.

[Alone-fxuh]

Can someone please explain those 3 lines?
if (map.containsKey(sum - k))
count += map.get(sum - k);
map.put(sum, map.getOrDefault(sum, 0) + 1);

[vivekkapoor]

Will it not have issue of double counting? Because we are doing result += map.get(sum-k)

[bistvijay]

public int subarraySum(int[] nums, int k) {

int count=0;
for(int i=0; i<nums.length-1; i++){

if(nums[i]+nums[i+1] == k){
count++;
}
}
return count;
}