Largest Subarray of sum K | Part2
Vložit
- čas přidán 7. 09. 2024
- [FREE] Beginners lessons in programming by Codechef - www.unacademy....
Patreon Link: / adityaverma
Video Pdf Notes And Code: / 44434748
Playlist Link: • Sliding Window Algorit...
Problem Description:
Given an array containing N positive integers and an integer K. Your task is to find the length of the longest Sub-Array with sum of the elements equal to the given value K.
For Input:
1
7 5
4 1 1 1 2 3 5
your output is:
4 .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
Q. Will the discussed approach work with negative numbers in the array?
A. No.
Because let's say in the given array [4,1,1,1,2,3,5] when we found the sum within the window to be greater than the desired value 5 (i=0, j=2 -> [4,1,1]), we started reducing the size of the window by doing i++. Here we assumed that once the sum of elements within the window becomes greater than 5 then increasing the window size will just add to the sum and hence we will not attain the sum 5 again. This is true when all the element are positive and hence reducing the window size by doing i++ makes sense. But this might not be true if array also contains negative numbers. Consider the array [4,1,1,-2,1,5], here we would have found the sum to be greater than 5 for i=0, j=2 and if we would have now started reducing the window size by doing i++, we would have missed the potential subarray (i=0, j=4).
In short, the discussed approach will not work with array having negative numbers.
Yes
poori video dekh kar comment kara kar
Do you have any diff soln for the negative numbers?
@@grovestreet9165 he replied because it was asked in video to explain. poora sun kr comment kia kro :p
Great Explanation Pratik ✌️ Pinning your comment so that others could be helped :)
To avoid doing the same if checks again when we shrink the window in case of sum > k, what we can do is place the check for sum > k in the beginning (after we increment sum). In this way, we can then check for both the cases i.e., sum == k and sum < k after we are done with sum > k check so that all the cases are covered.
Python Code for For an array with Positive Numbers ->
def largestSubarray(arr,k):
maxLength = 0
i,j = 0,0
sum = 0
while(j < len(arr)):
sum += arr[j]
# If sum becomes > k that means we have to shrink the window until the sum is no longer > k
if(sum > k):
while(sum > k):
sum -= arr[i]
i += 1
# If sum is equal to k then store the maximum of two lengths (previous length and curent length)
if(sum == k): maxLength = max(maxLength, (j - i + 1))
# Increase the window size
j += 1
return maxLength
int max = 0, s = 0, e = 0, sum = 0;
while(e < n){
sum += arr[e];
while(s k){
sum -= arr[s];
s++;
}
if(sum == k)
max = Math.max(max, e - s + 1);
e++;
}
return max;
// works for +ve/0 elements only
If possible, Graph series please!!
I think he had missed one check in this algo so many people are facing that it's not working for even positive numbers. Inside the while loop when "sum>k" , after decreasing sum = sum-arr[j], we have to check if (sum==k) then update max(result) variable. Look the code snippet below-
else if (sum>k){
while(sum>k){
sum = sum - arr[i];
i++;
if(sum==k){
max = Math.max(max,(j-i+1));
}
}
j++;
}
yes, correct!
@Mukul Panchal ya i figured it out after 1 min. of posting the comment but forgot to delete that.
j++ mat karo tab bhi baat ban jayegi itna likhne ki jarurat nahi padegi
We can simply put if(sum==k) after sum>k loop... Like.
if.. sum>k{
...}
if.. sum==k . {
....}
thnsk bro ,u are the real one man,im struck in this for soo long ,finallly someoe has explained this
Q. Will the discussed approach work with negative numbers in the array?
Ans. It won't work because 'j' is not further incremented, so there is always the possibility that -ve number might be present in the array that will again make the value that of sum, so we are not covering that possibility.
Below is code for the negative number using HashMap in O(n) time complexity:-
class GFG
{
public static void main (String[] args)
{
//code
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0){
int n=sc.nextInt();
int k=sc.nextInt();
int a[]=new int[n];
for(int i=0;i
bro, if sum till indexes are duplicates, then the hashmap will take the latest index value with the same sum as key, so one potential answer can be lost for e.g : 3 4 7 2 -3 1 7 2, k = 7-------map contents will be
3- > 0
7 -> 1
16 -> 3
13-> 4
14 -> 5
21 -> 6
22 -> 7
hance we wouldn't get the correct ans. Correct me if i m wrong
hats off to your understanding of algorithms, when u yourself understands to the depth then only one can teach like the way he's teaching
If sum > k then also we should check if sum == k or not
Test Case: {2,3,4,6,9,4} k=13
if(sum>k)
{
while(sum>k)
{
sum-=arr[i];
i++;
}
if(sum==k)
ws = max(ws,j-i+1);
j++;
}
yes we have to check
true
I had the same doubt . Thanks for clearing it.
for the best case, size will be size-1, so the size is not optimal, so no need to store it.
Update: yeah I was wrong as, its not necessary that earlier we had the solution.
true
Java code for the same:
int largestSubarray(int[] arr, int k){
int max = 0, sum = 0, i = 0, j = 0;
while(j < arr.length){
sum += arr[j];
if(sum < k){
j++;
}
else if(sum == k){
max = Math.max(max, j - i + 1);
j++;
}
else{
while(sum > k){
sum -= arr[i];
i++;
if(sum == k){
max = Math.max(max, j - i + 1);
}
}
j++;
}
}
return max;
}
Nyc
Please check for the testcase 2,3,4,6,7 and target is12
excellent bro ,saved lots of time
bro the code is good but it passes ony one test cse over gfg
//for postive + negative element. here we use prefix sum concept
/*
A[] = {10, 5, 2, 7, 1, 9}
K = 15
int main() {
int n,k;cin>>n>>k;
int arr[n];
for(auto &i:arr)
cin>>i;
mapm;
int s=0,mx=0;
for(int i=0;i
Hi Aditya,
You are doing good job. But one scenario came with this approach. Let's say -
int arr[] = {1,2,3,7,5};
int k = 12;
So if we remove arr[i] from sum(when i = 0), we should check again if sum == k
That was my observation.
yeah, you are right, in the third case before incrementing j, we need to check if the sum is equal to k and if it is then incorporate this window in our final answer.
This comment should be pinned
I think we should not include j++ inside sum>k condition @Mayank Jain
@@anshumishra8864 yup i was stuck for 2 hours and then i found ur cmmnt thnx brother.
I think that won't impact our final answer because we want the maximum length of the subarray, and if after incrementing i (sum==k), then the length of the subarray will surely be lesser than the length of the previous subarray.
int sum=0;
int ans=0;
HashMap map=new HashMap();
for(int i=0;i
For positive numbers under all the cases .
#include
using namespace std;
int solve(vector &A, const int &k) {
int n = A.size();
int i = 0, j = 0, sum = 0;
int mx = INT_MIN;
while (j < n) {
sum += A[j];
if (sum < k) {
j++;
} else if (sum == k) {
mx = max(mx, j - i + 1);
j++;
}
else if (sum>k){
while(sum>k){
sum = sum - A[i];
i++;
if(sum==k){
mx = max(mx,(j-i+1));
}
}
j++;
}
}
return mx;
}
For arr having negative elements.
Python Approach:
arr = [5,3,-15,7,8,8,-9]
s = 8
max_lst, t = [], []
i, j = 0, 0
while j < len(arr)-1:
if i < len(arr):
t.append(arr[i])
if sum(t) s or i == len(arr) -1:
t = []
j += 1
i = j
else:
i = 0
t = []
print(max(max_lst))
Code of the video and keep supporting aditya bro:
#include
#include
#include
using namespace std;
int solve(vector &A, const int &k) {
int n = A.size();
int i = 0, j = 0, sum = 0;
int mx = INT_MIN;
while (j < n) {
sum += A[j];
if (sum < k) {
j++;
} else if (sum == k) {
mx = max(mx, j - i + 1);
j++;
} else if (sum > k) {
while (sum > k) {
sum = sum - A[i];
i++;
}
j++;
}
}
return mx;
}
int main()
{
vector A{4, 1, 1, 1, 2, 3, 5};
int k = 5;
cout
negative numbers vale ka code bhi dede bro!!
negative k liye nhi chl raha h a{-13,0,6,15,16,2,15,-12, 17, -16, 0, -3, 19, -3, 2, -9, -6} sum=15
answer 5 h
@@avinash-xh6qw int lenOfLongSubarr(int A[], int n, int k)
{
// Complete the function
unordered_map mp;
int sum = 0 , maxLength = 0;
for(int i = 0 ; i < n ; ++i ){
sum += A[i];
if(mp.find(sum) == mp.end()){
mp[sum] = i;
}
if(mp.find(sum - k) != mp.end()){
maxLength = max(maxLength , i - mp[sum - k]);
}
if(sum == k){
maxLength = max(maxLength,i + 1);
}
}
return maxLength;
}
@@rithikdutt1332 Can you please explain this code?
A simple way to remember this is
- At every step you will increase j by exactly one
- Also at every step you may increase i by 0 or 1 or more than 1 depending on wether your condition is not met or overshot.
The algorithm used in explanation, in the example taken in the video {4,1,1,1,2,3,5} subarrays {2,3} and {5} are ignored. This is a bug and some of the tests will fail. For this to be handled in the else if(sum > targetSum) condition we need also check sum == targetSum after the while loop and recalculate the answer. Code below.
public class LargestSubArrayOfSumK {
public int lengthOfLargestSubArray(int[] arr, int targetSum){
int i=0, j=0, sum =0;
int max = Integer.MIN_VALUE;
while(i targetSum){
while(sum > targetSum){
sum = sum - arr[i];
i++;
}
if(sum == targetSum){
int tempAns = j-i+1;
max = Math.max(max, tempAns);
}
j++;
}
}
return max;
}
}
Absolutely right brother... I also got stuck in the same
bro used else if and he used only if due to this everytime loop will check the maximum , not to worry about that
When the condition below is reached,
if(sum>k)
{
while(sum>k)
{
sum -= v[i];
i++;
}
j++;
}
Here, after the loop breaks, before doing j++, we should also check whether sum == k or not, if (sum == k), then it is the candidate for maximum subarray length.
=> maxLen = max(maxLen, j-i+1); condition should be checked here as well.
So, the correct code for the condition sum>k should be as shown below:
if(sum>k)
{
while(sum>k)
{
sum -= v[i];
i++;
}
if(sum==k) maxLen = max(maxLen, j-i+1); //As this is also a candidate for maxLen.
j++;
}
you are correct
i got that too!! :)
pure logic , absolutely the best explanation
For Negative number we can use map as Aditya bro said.
int lenOfLongSubarr(int arr[], int n, int k)
{
//map to store the first index of any sum that's calculated
unordered_map mp;
int max=0,sum=0;
for(int i=0;imax)
max=i+1;
}
// sum(i,j)=sum(0,j)-sum(0,i),
//where sum(i,j) represents the sum of
//all the elements from index i to j-1.imax) max=len;
}
/*here came a lot of confusion, first I just simply
add first index of each sum to map (mp[sum]=i) but there came
problem when we had element 0 as the sum before encountering 0
is same as after encountering 0, so i put and if condition to check if
arr[i]!=0 only then add index to map,but that also failed, beacause there
are negative numbers,so for eg if sum 5 happens at index 4 then due to -ve and +ve
number it again sums at 5 at index 8 then i for that sum will be 8 instead of 4
as we need the first occurence of sum because that will give us maximum length,so
I put a if to check if the calculated sum is not in the map then only add index i to
corresponding map,otherwise dont, the if can be removed in case of smallest or minimum
subbarray length of with sum k*/
if(mp.find(sum)==mp.end())
mp[sum]=i;
}
return max;
}
For Negative number we can use map as Aditya bro said.
int lenOfLongSubarr(int arr[], int n, int k)
{
unordered_map mp;
int max=0,sum=0;
for(int i=0;imax)
max=i+1;
}
if(mp.find(sum-k)!=mp.end()) {
int len=i-mp[sum-k];
if(len>max) max=len;
}
if(mp.find(sum)==mp.end())
mp[sum]=i;
}
return max;
}
@@tarunkumar.d8379 bro what us the map used for??
@@tarunkumar.d8379 is*
@@adarsh443 Map is used for storing Key Value pair.
this approach won't work if array consist of negative numbers bcoz even if the sum becomes greater than required sum ,still we may find sum equal to required sum moving
along the array as we may encounter negative number which will reduce the sum back to required sum
What is the approach for this question with negative numbers in the array , if you have any idea pls tell me bro
@@sharanpreetchadha3579 u can try with hashmap ... that will definitely work... or u can approach this method as well but first of all u have to sort the array
I got confused at first when to use sliding window and when to use hashmap.. as a lot of similar questions can be solved by both the approaches. Now I am getting when to use these two. In this question, I think both the approaches will work. If there are -ve numbers too in the array then I think Hashmap(with prefix sum) approach should be preferred.
Sliding window approach in this question have O(1) space comp. but is using O(n^2) time. Whereas hashmap approach is using O(n) time and O(n) space complexity.
hi,could you please tell me about where to learn hashmaps or maps perfectly in similar kind of questions. I m having problem in some syntax part of maps.
@@pankhurigandhi625 maps are very usefull there is a video of luv of maps, you can watch it from there then practice some problems from gfg using tags.
a question guys ??
here in third condition i.e (k>sum)
we go on removing starting elements of sub array till (sum
right code needs little correction in the third case, add one more equal condition in the third case or i think we do not need second while loop and j++, first loop is sufficient but need to check it on code.
correct. I was tripped on this.
if we talk about -ve no. the condition is that when if sum>k our wheter sum >k it is possible it reach increse it size -ve no can make sum ==k that we can use sum>k
only valid if all the element in the array are positive otherwise need to use prefix sum approach
even that will be in O(NlogN). By using maps we can do it in O(N).
I will like to add an improvement too. In the condition while(sum >k) we are doing sum -= a[i]. We also have to check if sum == givensum before incrementing j.
Won't work on a testcase when
array : [1]
sum : 0
@@cybernaut001 what?
Yes
//FULL CODE AS EXPLAINED
int i = 0;
int j = 0;
int n = arr.length;
int sum = 0;
int mxl = Integer.MIN_VALUE;
while(j < n)
{
sum += arr[j];
if(sum > k)
{
while(sum > k) sum = sum - arr[i++];
//this is necessary because we have successfully handled case where we are adding and then checking with k
//what if we are subtracting and we get the result after it
//we come out of while loop in two cases ie either sum == k or sum < k
if(sum == k)
{
mxl = Math.max(mxl,j-i+1);
}
j++;
}
else if(sum == k)
{
mxl = Math.max(mxl,j-i+1);
j++;
}
else
{
j++;
}
}
return mxl;
if the discussed approach cant work for negative numbers then what changes should we make in this approach to get the correct code? What are the changes to be made in this code?
Or is it that sliding window cant be used for this question with negative numbers huh?
java easy readable solution for positive no -
private static int maxSubArrayLen(int[] input, int k) {
int maxLen = -1;
int start = 0, end = 0;
long sum = 0;
int len = input.length;
for (end = 0; end < len; end++) {
sum = sum + input[end];
while (sum > k) {
sum = sum - input[start];
start++;
}
if (sum == k) {
maxLen = Math.max(maxLen, end - start + 1);
}
}
return maxLen;
}
K=0
1 2 3 4
O/p----> -1
But your code doesn't work here so add a condition in while loop start < end
This Sliding Window / 2 pointer approach is optimal for array elements which are non-negative. For implementation of problem, with array having negative elements as well, the Hashmap approach is the most optimal one.
Nahi krti Negative ke case me.
Reason: When our sum is greater than k, we do i++ since j++ krne se kabhi Sum decrease nahi hoga agar sab positive hain. But if we have negative numbers, then we cant make that assumption
Bhai thank you for providing with such awesome explanation😇....looking forward to graph series...🤩
Shouldn't we do j++ only in sum
yes.. had the same doubt
code for only-positive elements array:
long long sum = 0;
long long mx = 0;
long long i=0, j = 0;
while(j < N){
sum = sum + A[j];
if(sum < K){
j++;
}else if(sum == K){
mx = max(mx,j-i+1);
j++;
}else if(sum > K){
while(sum >= K){
sum -= A[i];
i++;
}
j++;
}
}
actual mudda starts at 10:00
For negative integers including solution:
int lenOfLongSubarr(int arr[], int n, int k)
{
// Complete the function
long long int sum=0,cnt=0,j=0,i=0,ans=0;
map mp;
while(j
sir, please upload on "Greedy algo".
This solution will not work if there are negative elements in the array, because here what we are doing is whenever sum is becoming greater than K, we are just increasing i but it might possible that even if the sum is greater than k and some negative elements are present ahead then sum will reduce and can become equal to K again and window will be larger !
eg. arr[4] = {1,2,4,-1}, K=6, you solution will give answer as 2 but the answer is 4.
Q. Will the discussed approach work with negative numbers in the array?
A.yes applicable na sir because if desired sum
dryrun this testcase then you will get your answer [4,1,1,-2,1,5] maxmim lengh possible here for k =5 is 5 try out with current algo and check it
Q. Will the discussed approach work with negative numbers in the array?
A. No. because we are not able to reduce the sum.
code for +ve numbers
while(jk)
{
sum-=nums[i];
i++;
}
j++;
}
else if(sum==k)
{
mx=max(mx, j-i+1);
j++;
}
}
cout
what will be output for array [10,2,13,7,1,9] and sum equal to 15 . According to your code output will be 0 but it must be 2 as 2 + 13 = 15
Aditya's videos are so good by now I'm easily able to solve the code by just watching his video till the problem statement.
More easy to understand code:
int maxLen(int arr[],int n,int k){
int i=0,j=0,sum=0,res=0;
while(j
wrong code. your code is showing tle
It seems some of the conditions were missing, Below is the c# working code
public static int VariableSlidingWindow(int[] array, long sum)
{
int localSum = 0;
int j = 0;
int i = 0;
int max = 0;
while (j < array.Length)
{
localSum = localSum + array[j];
if(localSum == sum)
{
if((j-i+1) > max)
{
max = (j-i +1);
}
}
else
{
while(localSum > sum)
{
localSum -= array[i];
i++;
if (localSum == sum)
{
max = Math.Max(max, (j - i + 1));
}
}
}
j++;
}
return max;
}
thanks brother
Yes we need to check for max in greater than case as well while removing ith value
To solve this problem with Array containing negative and positive numbers ...we have to use hashmap ...so this will no longer be a problem of Sliding Window concept
sliding window approach might works for this question but it is not the best approach ,instead use prefix sum approach
This approach has TC:O(n) and SC:O(1) whereas the prefix sum will have TC:O(n) and SC:(n). This solution is optimal if all the numbers are >=0
Sir you are the best.
Thank u😊😊.
Please keep uploading according to your time limitations
It’s a good approach if array contains only positive numbers. But if it contains both positive and negative integers then use hashMap it will be more easy as this approach is not working in that case.
This code won't work even for all +ve numbers. Let's say k = 5 , for case {2,1,1,3,1} at j=3, sum is 7. On removing arr[0] it becomes 5 which is equal to k. Incrementing j without checking will miss this case.
#include
// work only for positive numbers
using namespace std;
int main(){
int n;
cin >> n;
int sum, temp = 0, ans = 0;
cin >> sum;
int* arr = new int[n];
for(int i=0; i> arr[i];
}
int i = 0, j = 0;
while(j < n){
temp += arr[j];
if(temp == sum){
ans = max(ans, j - i + 1);
j++;
}
else if(temp < sum){
j++;
}
else if(temp > sum){
while(temp > sum){
temp -= arr[i];
i++;
}
j++;
}
}
if(temp == sum){
ans = max(ans, j - i + 1);
}
cout
@@Jonathan-ng4vw Why u are checking temp == sum twice?
It will be covered in above condn. alone.
Answer for array having negative numbers with map:
def solve(arr,k):
hash = {}
total,maxl =0,0
for i in range(len(arr)):
total+=arr[i]
if total==k:
maxl=i+1
elif total-k in hash:
maxl = max(maxl, i-hash[total-k])
if total not in hash:
hash[total]=i
return maxl
Could you please explain your approach??
Java Code For Reference:-
private static int longestSubArraySum(int[] arr,int targetSum) {
int start = 0,end = 0;
int maxValue = Integer.MIN_VALUE;
int tempSum = 0;
while(end < arr.length) {
tempSum += arr[end];
if(tempSum < targetSum) {
end++;
} else if(tempSum == targetSum) {
maxValue = Math.max(maxValue,(end-start+1));
end++;
} else if(tempSum > targetSum) {
while(tempSum > targetSum) {
tempSum -= arr[start];
start++;
}
end++;
}
}
return maxValue;
}
# Given an array of integers, our goal is to find the length of the largest subarray having the sum of its elements = ‘k’
def long_subarray(arr, k):
n = len(arr)
sum = 0
win_size = 0
i = 0
j = 0
while j < n:
sum = sum + arr[j]
if sum == k:
win_size = max(win_size, j-i+1)
elif sum > k:
while sum > k and i
Congratulations bhai for 90k
I am happy and glad to be part of this journey ❣️❣️
------------------please give attention in the (sum>k) wala part---------------------------------------
------------------only for positive numbers including zero-------------------------------------------------
#include
int longestSubarrayWithSumK(vector nums, long long k) {
int n=nums.size();
int maxlen=0;
int i=0;
int j=0;
long long sum=0;
while(j
we can use Kadane's algorithm for both +ve and -ve numbers.
how, can u plz explain
kadane's element wont give the maximum size subarray
@@harshkumar-pd3ws kadane's algo along with hash-table
@@akshay-kumar-007 can you send me the code using your method
can u please explain in detail?? 🥺
SIR,
When we increment j in the third case when sum>k we are losing a potential answer isn't it?
Consider [1,1,1,4] and k=6 so when j will come to "4" if we increment j we won't get any output resulting in 0 hence we will lose the potential ans.
Yes, even I noticed that when the sum will be equal to a condition in the third case, we are not saving that and incrementing the j, resulting in loss of potential answer.
@@ShivaniSingh-sf3mv exactly
Debo Doley 😜🤣
@@gaurabdas1510 Grow up kid
Even i noticed that bt this can be overcome by interchanging the place of 3rd and 2nd condition
*Java Code 100% working:*
public static int maximumSubarraySumEqualsK(int[] nums, int k) {
int i=0, j=0;
int max = 0;
int sum = 0;
while(j < nums.length) {
sum = sum + nums[j];
if(sum < k) {
j++;
}
else if(sum > k) {
while(sum > k) {
sum = sum - nums[i];
i++;
}
if(sum == k) {
max = Math.max(max, (j-i+1));
j++;
} else {
j++;
}
}
else if(sum == k) {
max = Math.max(max, (j-i+1));
j++;
}
}
return max;
}
I think this will work for all cases
#include
using namespace std;
int main()
{
vector arr={3,2,20,1,1,3};
int k=20,start=0,end=0,sum=0,ans=0;
while(endk)
{
sum-=arr[start];
start++;
}
if(sum==k)
{
ans=max(ans,end-start+1);
}
end++;
}
cout
i even solved this problem without watching its second part, that's the power of concept
JAVASCRIPT SOLUTION :-
let array = [4,1,1,1,2,3,5]
let k = 5
function solve(array,k) {
let j = 0;
let i = 0;
let max = 0
let sum = 0
while (j < array.length) {
sum += array[j]
if(sum < k){
j++
}else{
max = Math.max(max, j - i + 1)
sum = sum - array[i]
j++
i++
}
}
return max
}
console.log(solve(array,k))
Your approach doesn't even work for positive integers.
Eg:- 3,1,4,2
K=5
Correct answer=2
Your answer=0
Bro include sum==k condition inside while
While(sum>k)
{
Sum =summary[i];
i++;
If(sum==k) {
Math. Max(max, j-i+1)
}
}
It will work if we just update our k and arrays element to positive. we can do it by simply adding minimum negative number in arrays to k and all elements of the arrays . this will result in array to be all positive numbers and same algo can work for k+Absolute(minNegativeElement) .
can i say all subarray questions can be solved with sliding window approach
Java code for above explanation (won't work if numbers are negative)
int[] nums = {4,1,1,1,2,3,5};
int k = 5,n=7;
int i=0,j=0;
int sum = 0;
int max = 0;
while(jk) {
sum -= nums[i];
i++;
j++;
}
}
}
System.out.println(max);
Java Code ->
private static int longestSubArraySum(int[] arr,int targetSum) {
int start = 0,end = 0;
int maxValue = Integer.MIN_VALUE;
int tempSum = 0;
while(end < arr.length) {
tempSum += arr[end];
if(tempSum < targetSum) {
end++;
} else if(tempSum == targetSum) {
maxValue = Math.max(maxValue,(end-start+1));
end++;
} else if(tempSum > targetSum) {
while(tempSum > targetSum) {
tempSum -= arr[start];
start++;
}
end++;
}
}
return maxValue;
}
There is a problem in your code. If the sum>k, then we start removing element with increment in i, but if after removing element the sum again get equal to k. This candidate is left.
Ex:- 4,1,4,1,2,3,5 and k=5
In this example if i=0 and j=2 then, sum=9. Now we start removing elements from left. So first we remove 4, then the sum will be again 5. But after the while loop we are not checking the sum==k.
So, after the while loop in (sum>k) we must chekc whether the sum==k or not.
I had the same doubt and was breaking my head on this!
Thanks for your comment 🤝🏽
@@syedsalman7737 thx god finally someone atleast notice from last half an hour i am just wondering
can we use kadanes algorithm??
int maximum_subarray_length_with_given_sum(vector v , int k)
{
int n = v.size() ;
map m ;
m[0] = -1 ;
int mx = 0 , sum = 0 ;
for(int i=0 ; i
const arr = [1, 1, 1, 1, 0, 1];
function largestSubArrayOfSumK(arr, k) {
let [start, end, res, sum] = [0, 0, 0, 0];
while (end < arr.length) {
if (sum < k) {
sum = sum + arr[end];
end++;
}
if (sum === k) {
res = Math.max(res, end - start);
sum = sum + arr[end];
end++;
}
if (sum > k) {
while (sum > k) {
sum = sum - arr[start];
start++;
}
}
}
return res;
}
console.log(largestSubArrayOfSumK(arr, 5));
if (sum>targetSum)
isme if sum becomes equal to target sum, then why are we incrementing j
not able to understand this
I will like to add an improvement. In the condition where sum==k, we also have to update the sum before i++ i.e. sum=sum-a[i]
No need to do this as it will be covered under sum>k loop in next iteration.
@@shashijaiswal5014 but in if(sum==k) if we dont update sum then it keep on hitting this if loop only since always sum will be k.CAN ANYONE CAME UP TO SOLVE THIS?
@@Techjai000 but when first while loop starts we have increment sum without any condition so (sum==k) never hit again and again
// Variable Subarry of sum k
// Given an array containing N positive integers and an integer K.
// Your task is to find the length of the longest Sub-Array with sum of the elements equal to the given value K.
// For Input:
// 1
// 7 5
// 4 1 1 1 2 3 5
// your output is:
// 4 .
#include
using namespace std;
int longestSubArr(int *arr,int n,int k)
{
int i=0,j=0;
int sum=0;
int maxSize=INT_MIN;
while(jk){
sum=sum-arr[i];
i++;
}
j++;
}
}
return maxSize;
}
int main()
{
int n,sum;
cin>>n>>sum;
int *arr=new int[n];
for(int i=0;i>arr[i];
}
cout
Not work for negative numbers because the assumption is when sum is greater than k we are incrementing i to decrease the the sum sum-i but if it is negative the sum value further increase
bro in which year u r in ?
lets connect on linkdin i m also doing sliding window playlist .
if anyone is looking for the JAVA sol
public static void main(String[] args) {
int[] arr= {4,1,1,1,2,3,5};
int k=5;
long sum=0;
int i=0,j=0;
int maxSize= Integer.MIN_VALUE;
while(jk) {
sum= sum- arr[i];
i++;
if(sum==k) {
maxSize= Math.max(maxSize, j-i+1);
}
}
j++;
}
}
System.out.println(maxSize);
}
Sir please videos jaldi upload kiya kro. Ur videos are really very helpful 🙏🙏
Java Code :
package slidingWindow.variableSize;
public class LargestSubArrOfSumK {
public static void main(String[] args) {
int[] arr = { 4, 1, 1, 1, 2, 3, 5 };
int k = 3;
getLargestSubArr(arr, k);
}
private static void getLargestSubArr(int[] arr, int k) {
int start = 0, end = 0, sum = 0, maxSubArr = 0;
while (end < arr.length) {
sum += arr[end];
if (sum < k) {
end++;
} else if (sum == k) {
System.out.println("possible answer: " + (end - start + 1));
maxSubArr = Math.max(maxSubArr, (end - start + 1));
end++;
} else // sum>k
{
while (sum > k) {
sum = sum - arr[start];
start++;
}
if (sum == k) {
System.out.println("possible answer: " + (end - start + 1));
maxSubArr = Math.max(maxSubArr, (end - start + 1));
}
end++;
}
}
System.out.println(maxSubArr);
}
}
what is the time complexity? how to find it. Outer loop runs O(n) times what about inner loop in terms of worst case.
No this won't work for the -ve Integers.
Suppose the given exp by you i.e [-5,8,-14,2,4,12], so when we are traversing this array and matching the sum with given K .In the first case when i=0,j=0 we are getting the sum as -5 which is equal to K and we got length as 1, now when we are further iterating i=0,j=1 then sum is getting greater than K and when we are decreasing the window i++ then condition won't and we won't achieve the answer.
// THIS CODE WILL NOT WORK FOR NEGATIVE ELEMENTS JUST FOR UNDERSTANDING OF THE FOLLOWING EXAMPLE
#include
using namespace std;
int subarray(int arr[], int n, int k)
{
int maxi = INT_MIN; int sum=0;
int i=0,j=0;
while(j k)
{
while(sum > k)
{
sum-=arr[i];
i++;
}
flag=1;
}
else if(sum==k)
{
maxi = max(maxi,j-i+1);
j++;
flag=0;
}
if(flag)
j++;
}
}
return maxi;
}
int main()
{
int n=7,k=5;
int arr[n] = {4,1,1,1,2,3,5};
int ans = subarray(arr,n,k);
cout
18:00 he incorrectly wrote j++ for sum>k. It should be i++. J is incremented only till we reach k value. Once we have breached k value then arr(i) is subtracted from sum and i is incremented for next iteration.
Code in JAVA that works for both positive and positive negative included !
class Solution{
public static int lenOfLongSubarr (int arr[], int n, int k) {
HashMap map = new HashMap();
int max = 0;
int sum = 0;
for(int i=0;i
Its not a sliding window approch
Thanks Aditya! I implemented this method as explain and it works fine for me. For the given set array in the video {4, 1, 1, 1, 2, 3, 5} on debugging i came to know that the last element (5) with a window size 1 is never calculated. I was wondering if the problem was to find the smallest window for target Sum 5 instead of largest window, it would give 2 (4+1) instead of 1 (5). Please let me know if I've made any mistake in the code:
public static int LargestSubArrayOfSum(int[] array, int targetSum)
{
int start = 0;
int sum = 0;
int maxWindow = int.MinValue;
for (int end = 0; end < array.Length; end++)
{
sum += array[end];
if (sum == targetSum)
{
maxWindow = Math.Max(end - start + 1, maxWindow);
}
while (sum > targetSum)
{
sum -= array[start];
start++;
}
}
return maxWindow;
}
I know I am very late, but I am gonna try to help. I do not use the language that you are using so I can't run, but from the first glance, it seems like the issue is with your loop condition. Try to use the '
@@priteshsoni3891 how this solution will work if we need to find out shortest subarray which does not exceed given sum ?
@@ShivamSharma-is8ep we just have to use Math.min function instead of Math.max
Not working for arr=[1,1,5] k=5
Should return 1. Returning 0 instead
Another ex: arr=[1,1,5,1,1,2,5] k=5
You can add a check if(sum == k) in "sum > k" section while reducing arr[i] and save the result.
else if(sum > k){
while(sum > k){
sum = sum - arr[i];
++i;
if(sum == k) { res = max(res, j - i + 1); }
}
++j;
}
@@sahilguleria5505 yes, we need to add the code snippet you mentioned above. If we don't add it we'll end up loosing the case where the sum is exactly k while reducing the sum
@@sahilguleria5505 it is even not working when ar=[1] and k=0 ans should be 0 but it gives 1
@@sahilguleria5505 Dude u totally saved my day
JAVA | FOR POSITIVE NUMBER ONLY
class Solution {
public int subarraySum(int[] nums, int k) {
if(k == 0) {
return 0;
}
int i = 0 ;
int j = 0;
int sum = 0;
int ans = 0;
while(j < nums.length) {
sum += nums[j];
if(sum < k) {
j++;
} else if(sum == k) {
ans++;
j++;
} else {
while(sum > k) {
sum -= nums[i];
i++;
}
if(sum == k) ans++;
j++;
}
}
return ans;
}
}
Finally.....The king is back!!!!
And youbthe Queen😂
*you the
for -ve numbers
class Solution {
public:
int lenOfLongSubarr(vector& v, int n, int k){
int ans = 0;
unordered_map u;
u[0] = 1;
int psum = 0;
for(int i=0;i
Belated Happy birthday sir ji .. 🙏❣
Not possible
let us consider array [4,1,1,-1]
for sum = 5
from i=0 to i=1 we get [4,1]
from i=0 to i=2 sum = 6
so we will i++
but we miss from i=0 to i =3 we get [4,1,1,-1]
simple JS approach
function largestSubArrayOfSumK(arr, k) {
let sum = 0;
let ans = 0;
let end = 0;
let start = 0;
while (end < arr.length) {
if (sum < k) {
sum += arr[end];
end++;
}
if (sum === k) {
ans = Math.max(ans, end - start);
sum += arr[end];
end++;
sum -= arr[start];
start++;
}
if (sum > k) {
sum -= arr[start];
start++;
}
}
return(ans);
}
//Solution for negative elements inside array
int lenOfLongSubarr(int A[], int N, int K)
{
int ans=0;
int sum=0;
unordered_map preSum;
preSum.insert({0,-1});
for(int i=0;i
in case: sum > k you said i++..what it i becomes > j?
For negative numbers - You can use a map. The standard solution is prefix sum. Worth exploring.
Bro Can u please share the approach it will be very usefull to us.
@@tennetisaisarath2349 just google prefix sum. You'll get it. It's a very common technique
@@tennetisaisarath2349 you can check striver's video for same topic where he had explained that approach
Then how will we approach for negative number for this type of problem?
++
What if negative numbers are also there.. how to decide then? Whether to move j or move i ??
Apart from negative numbers , i think this method will also not work if 0 is present in the array
0 won't put the algo in jeopardy
Bhaiya apki approach se negetive numbers nhi handel ho rhe hai, please share code by your approach which can handle neg no to .
This code will crash fot negative numbers because now if you increase slide(j++), sum might not be increasing and if you decrease slide(i++), sum might not be decreasing.
Hi Aditya,
Your explanations are really good, but this solution seems to be incorrect :
try your approach with [4,1,4,5,3,2,1,2,1,1] with k = 5.
The 3 If condition will be called when j=2. This will increment i by 1, thus making the sub array as [1,4] and the sum will change to [9-4 = 5]. Since this sum is not > 5, the j++ will be executed and main loop will change the sum to 10. The sub array now becomes [1,4,5] and hence sum = 10.
We missed a pair 1,4 here.
We can change the 3rd condition as below to allow this scenario as well :
if(sum > k )
{ sum = sum -ar[i] - ar[j];
++ i ;
}
This will just increment the i to remove the first element of window. Since the main while loop will add ar[j] again to the sum , we are subtracting that in 3rd condition.
else if (currentSum sum) {
currentSum -= a[i];
i++;
}
//this part is missing, after decreasing the window, we might also encounter currentSum == sum, hence add a check in third condition and this will work
if (currentSum == sum) {
count=Math.max(count,j-i+1);
}
j++;
}
✅✅✅✅
Loop will happen again no need to check j++ will not happen try to understand as while loop will exit when equal conditon
for neqative numbers, extension of LEETCODE 560 problem will be applied .
Hi Aditya, You are explaining well, but try to keep the videos short as I cansee same sentences have been repeated so many times, I try to skip repeated stuff and i miss something important, respect viewers time, and keep videos Precise, spending 46min for this explanation is too much, and try to give snapshot of entire code again at the end of video, rest all good. Appreciate your efforts.✌
Python code:
A = [4, 1, 1, 1, 2, 3, 5]
k = 5
n = len(A)
i = 0
j = 0
total = 0
maxL = float('-inf')
while j < n:
# 1. Calculation
total += A[j]
if total < k:
j += 1
elif total == k:
maxL = max(maxL, j - i + 1)
j += 1
else:
while total > k:
total -= A[i]
i += 1
j += 1
print(f"Largest Subarray of Sum {k} has size: ", maxL)
I think the solution fails for this arr :
int arr[] = {1,4,20,3,10,5};
int k = 33;
This is my code..
public int solultionSlidingWindow(int [] arr, int k) {
// this solution won't work for negative numbers
int resultLen = 0;
int start = 0;
int end = 0;
int movingSum = 0;
while (end < arr.length) {
//System.out.println(arr[end] +" to "+ arr[end]);
movingSum = movingSum + arr[end];
if(movingSum < k) {
end++;
}
else if(k == movingSum) {
System.out.println("equal :" + arr[end] +" to "+ arr[end]);
resultLen = Math.max(resultLen, end - start + 1);
end++;
}
else if( movingSum > k) {
while(movingSum > k) {
movingSum = movingSum - arr[start];
start++;
}
end++;
}
}
return resultLen;
}
Thank you very much. You are a genius.
No it doesnt works for negatives {-13 0 6 15 16 2 15 -12 17 -16 0 -3 19 -3 2 -9 -6} with sum=15
constraints say that 0
Great video but missed one edge case I guess. Will this code work with inputs :-
arr -> [4, 1, 2, 3, 1, 6, 1, 1, 4]
sum -> 5