It becomes hard problem when we try to solve using sliding window but how easily Striver was able to explain it is just Awesome and much appreciated❤❤❤
Code : class Solution { public: int lessequaltok(vector& nums,int goal){ if(goal < 0) return 0; int l = 0; int r = 0; int ans = 0; int n = nums.size(); int sum = 0; while(r < n){ sum += nums[r]; while(sum > goal){ sum -= nums[l]; l++; } ans += (r-l+1); r++; } return ans; } int numSubarraysWithSum(vector& nums, int goal) { return lessequaltok(nums,goal)-lessequaltok(nums,goal-1); } };
This is an Excellent Question, truly amazing tutorial striver. Kudos to you bro. Striver only heap and stack queues are left, hoping to get those series soon. Take care of your health bro. The entire DSA community will forever be indebted to you.
I am unable to understand why fun(nums,goal) - fun(nums,goal-1) works here? What's the math here? I am unable to understand this basic maths behind it, please can anyone explain me the maths behind this?
please watch A - B in this video ( ru-vid.com3uaVqX5qClg?si=c2yO4X4gQwXrqm3u ) continue reading after watching the video. draw the venn diagram of A-B on paper and refer to it while reading this comment for better understanding. lets assume you need people who have 2 rupees that is ( fun(nums,goal) here we are finding people who
class Solution { public: int count(vector& nums, int goal) { int left = 0; int right = 0; int sum = 0; int count = 0; // if() while (right < nums.size()) { sum += nums[right]; while (sum > goal && left
@@chakrabarti9634 Dekh bhai example se samjthe hai let goal=2 Calculate helpMe(nums, goal) This function will count all subarrays with sums less than or equal to 2. Subarrays with sum 0: [] Subarrays with sum 1: [1], [0], [1], [0], [1], [1,0], [0,1], [1], [1,0] Subarrays with sum 2: [1,0,1], [0,1,0], [1,0,1], [1,0], [0,1,0,1], [1,0,1], [1,0,1] Calculate helpMe(nums, goal - 1) This function will count all subarrays with sums less than or equal to 1. Subarrays with sum 0: [] Subarrays with sum 1: [1], [0], [1], [0], [1], [1,0], [0,1], [1], [1,0] Find the Exact Count The number of subarrays with sum exactly 2 is helpMe(nums, 2) - helpMe(nums, 1). Aya samjh....
the solution is amazing ...opened up my mind..superb explanation but i wonder striver did it so easily when will i be able to build such intuition ... i got great confidence throughout the playlist but the way sir brought up the solution amazed me but also gave lot of questions as to when will i be able to think like this
Honestly for subarray sum problems having negative values or 0s , prefixSum is the way to go. It's slightly less performant but more intuitive. I tried learning the optmized approach several times but its too clever and unlikely to come up with during interview given that we have so many other data structures, algs patterns to worry about already lol. Problems w/ prefixSum: subarray sum equals k, binary sum equals k , nice subarrays(SAME logic as binary sum w/ slight change).
And thats completely fine. Consider them as like Mathematical formulas. Recall that without having learned formulas, it would be nearly impossible to solve even simple math problems. Unfortunately these patterns are not covered in traditional CS curriculums where we just learn data structures, and common algorithms like traversals ,insertions ,deletions. Also another common pattern/strategy is to use the prefixSum solution. You shouldn't feel like you have to come up with these patterns on your own...just like math formulas lol.
class Solution { public: int fun(vector& arr, int goal){ if(goal < 0 ) return 0; int l = 0, r = 0 , cnt = 0; int sum = 0; while(r < arr.size()){ sum += arr[r]; while(sum > goal){ sum -= arr[l]; l++; } cnt += r - l + 1; r++; } return cnt; } int numSubarraysWithSum(vector& nums, int goal) { return fun(nums,goal) - fun(nums,goal - 1); } };
this type -> we have to count the no of subarrays normal sliding windows -> we have to find longest length subarray watch video 1 of the playlist and refer type 2 and type 3 problems in the vid
this is the solution that raj bhaiya told us do at last goal-goal-1; class Solution { public: int numSubarraysWithSum(vector& nums, int goal) { int l=0; int r= 0; int count =0; int sum = 0 ; while(r < nums.size()){ sum = sum+ nums[r]; while(sum>goal){ sum = sum -nums[l]; l++; } if(sum
At 16:15 I am getting problem here. Why are we considering all the count of r-l+1 when we only get 1 count instead of 4 in the case of 1001? The same problem got reflected in leetcode too, getting wrong answer in test cases. Solution: watch lecture 11 to understand in detail. The code is correct if goal is
anyone fix this class Solution { public int numSubarraysWithSum(int[] arr, int k) { int n = arr.length, count = 0, sum = 0, r= 0, l = 0; while(r < n){ sum += arr[r]; while(sum > k){ sum -= arr[l]; l++; } if(sum == k){ count += r - l + 1; } r++; } return count; } }
@abhaysinhgaikwad Hi brother, class Solution { public int func(int[] arr, int k) { int sum = 0, l = 0, r = 0, count = 0; if (k < 0) return 0; while (r < arr.length) { sum += arr[r]; while (sum > k) { sum -= arr[l]; l++; } if (sum
import java.util.HashMap; class Solution { public int numSubarraysWithSum(int[] nums, int goal) { int sum = 0; int count = 0; HashMap prefixSums = new HashMap(); prefixSums.put(0, 1); // There's one way to have a sum of 0, by taking no elements. for (int num : nums) { sum += num; // If sum - goal has been seen before, it means there's a subarray ending at the current index // which sums to the goal. if (prefixSums.containsKey(sum - goal)) { count += prefixSums.get(sum - goal); } // Add the current sum to the map of prefix sums. prefixSums.put(sum, prefixSums.getOrDefault(sum, 0) + 1); } return count; } }
Since the array is 0-Indexed. Indexing -> 0,1,2,3 for example nums = {6,4,3,7} nums.size() would be 4, So ultimately we would be accessing the index which is out of bounds
Well, I had the same doubt, I realized that in the original problem, the goal or K can be negative. This algorithm fails to handle negative sum value. Also try dry running for this case {-1, -1, 1} with k = 0, you will get the answer as zero. But the correct answer should be 1. Why this algorithm fails? It is because the overall sum b/w left & right can be less than K, but the current element pointed by right is where we are not sure of it, whether it is less than equal to K or not. And this algo add that case in the overall count. Basically, this algo fails to handle negative integers. If someone has a better explanation, please continue this thread.
