Largest Subarray of sum K | Part2
Вставка
- Опубліковано 1 жов 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 :)
If possible, Graph series please!!
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
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
sir, please upload on "Greedy algo".
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?
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).
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
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
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.
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.
can i say all subarray questions can be solved with sliding window approach
Seriously you took 2 videos of 25 minutes to explain this. It feels time waste, in 50 minutes a lot can happen. Explaining fixed problem again and again and then repeating the same thing, is kind of irritating.
Try for shorter videos too.
bruh! and he couldve done a "lot of things" instead of making free videos for you
bhaiya GRAPH GRAPH GRAPH GRAPH GRAPH GRAPH CHAHIYE. PLEASE PLEASE PLEASE. BANADO ASAP
madam ek bar likhogi tb bhi samaj aa jayega
@@minkiaggarwall5529 🤣🤣🤣👍
@@manasasb536 good i think bhaiya jaldi bana denge students ki masumiyat dekh kar
aditya verma ki aukaat nahi hai ki graph jaise topic padha sake, ye sb easy topics bana ke bas audience gain krrha hai
@@TuringTested01ha toh ja ke apne baap se condom kyu use nhi kiya jo tere jesa c peda ho gya jo idhar udhar jake apni g mrata rhta h...nikal lawde
Meri okat dekhega
can we use kadanes algorithm??
sir backtracking kab aaegi???
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.
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
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)
}
}
*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;
}
Bhai thank you for providing with such awesome explanation😇....looking forward to graph series...🤩
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
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?
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
c++ (map solution)
unordered_map mp ;
int sum =0;
int maxi =0;
// test case -- 10 5 2 4 3 1 6
for(int i = 0 ; i
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.
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
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.
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
is anyone use this approach find shortest subarray which does not exceed given sum like below example :-
int[] arr1 = { 1, 3, 7, 2,8 }; given sum is 7 and answer is 1 because 7 is the shortest subarray which does not exceed given sum 7
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
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.
###### CORRECTED CODE ###########################
Hello Sir When Our Window is Shrinking after that your code will not check for
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 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
good explanation but so much distraction. You always mix your old problem with new. I am following your series and you always take us back to first video and its distracting at least for me.
if (sum>targetSum)
isme if sum becomes equal to target sum, then why are we incrementing j
not able to understand this
pure logic , absolutely the best explanation
Hope this guy will back with graph backtracking and tree??? Where is you!!!
// java implementation:
@Description("This works ONLY on non-negative integers")
public static int lengthOfLongestSubArray(int[] arr, int n, int k) {
int j = 0, i = 0, sum = 0;
int ans = Integer.MIN_VALUE;
while (j < n) {
sum += arr[j];
if (sum < k) {
j++;
} else if (sum == k) {
ans = Math.max(ans, j - i + 1);
j++;
} else {
while (sum > k) {
sum -= arr[i];
i++;
}
j++;
}
}
return ans;
}
// Compact way
private static int lengthOfLongestSubArray2(int[] arr, int n, int k) {
int i = 0, sum = 0;
int ans = Integer.MIN_VALUE;
for (int j = 0; j < n; j++) {
sum += arr[j];
if (sum == k) ans = Math.max(ans, (j - i + 1));
while (sum > k) sum -= arr[i++];
}
return ans;
}
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
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
Then how will we approach for negative number for this type of problem?
++
Sir you are the best.
Thank u😊😊.
Please keep uploading according to your time limitations
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
in case: sum > k you said i++..what it i becomes > j?
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);
}
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?? 🥺
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;
}
Bhai i tried question but some test cases did not pass
int sum=0;
int ans=0;
HashMap map=new HashMap();
for(int i=0;i
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.
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));
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.✌
Why don’t we learn the approach in one go.
This approach is not useful for arr containing zero and negative numbers
Java Code ||
i
import java.io.*;
import java.util.*;
public class LargestSubArrayOfKPositiveNumbersOnly {
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int T=Integer.parseInt(br.readLine().trim());
while(T-->0) {
int n=Integer.parseInt(br.readLine().trim());
String[] str=br.readLine().trim().split(" ");
int arr[]=new int[n];
for(int i=0;i
private static void solveWithNegativeIntegers(int[] array, int k) {
int sum = 0;
Map map = new HashMap();
map.put(0,0);
int maxLength = Integer.MIN_VALUE;
for (int i = 0;i < array.length;i++){
sum += array[i];
if(map.containsKey(sum - k)){ // sub array found
maxLength = Math.max(maxLength,i- map.get(sum-k)+1);
System.out.println("Subarray found : "+map.get(sum-k)+" "+i);
}
map.put(sum,i+1);
}
System.out.println(maxLength);
}
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.
I can't believe that the solution given in gfg site itself is giving me wrong answer when I copy pasted it 😂😂😂😂
[-1,1,0] k equal
To 0 pe kuch check hi ni kr paaya
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))
I hope the above logic is not going to work in all the above cases. suppose the test case is 2 3 1 2 4 3 in this case the answer will be hit only in the condition when we will remove some calculations., and therefore after the calculation, we will do j++ in the end the answer will be missed.
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;
}
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
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.
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;
}
}
\\ this will work fine for -ve numbers...
unordered_map mp;
int sum=0,ans=0;
mp[0]=1;
for(int i=0;i
last example -5,8,-14,2,4,12, sum = 6,, cannot be achieved. so this method not works
Longest Sub-Array of Sum K with Negative (Code in C++) (GFG)
class Solution{
public:
int lenOfLongSubarr(int A[], int N, int K)
{
// Complete the function
int len=0;
int sum=0;
unordered_mapmp;
for(int i=0;i
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.
private static void solveWithNegativeIntegers(int[] array, int k) {
int sum = 0;
Map map = new HashMap();
map.put(0,0);
int maxLength = Integer.MIN_VALUE;
for (int i = 0;i < array.length;i++){
sum += array[i];
if(map.containsKey(sum - k)){ // sub array found
maxLength = Math.max(maxLength,i- map.get(sum-k)+1);
System.out.println("Subarray found : "+map.get(sum-k)+" "+i);
}
map.put(sum,i+1);
}
System.out.println(maxLength);
}
When will be the graph series coming.
------------------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
ye question leet code pe h?
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.
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);
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
Sir please videos jaldi upload kiya kro. Ur videos are really very helpful 🙏🙏
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
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
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
int i=0;
int j=0;
int sum=0;
int len=0;
// vector ans;
// if(k==0)
// {
// ans.push_back(-1);
// return ans;
// }
while(i
If it helps someone, i will be happy.
int lenOfLongSubarr(int A[], int N, int K)
{
unordered_mapmp;
mp[0]=0;
int sum=0;
int maxi=0;
for(int i=0;i
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;
Belated Happy birthday sir ji .. 🙏❣
Congratulations bhai for 90k
I am happy and glad to be part of this journey ❣️❣️
Code if all Elm is +ve:
int lenOfLongSubarr(int A[], int N, int K)
{
// Complete the function
int i=0;
int j=0;
int sum=0;
int ans=0;
while(jK)
{
while(sum>K)
{
sum = sum-A[i];
i++;
}
if(sum==K). // this is imp step
{
ans = max(ans,(j-i+1));
}
j++;
}
}
return ans;
}
can u run this code for array=[1,2,1,3] ; k(sum)=2....mine is giving wrong answer using your method
if it runs well plz share the code
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
Thanks, understood :)
Sep'26, 2023 06:50 pm
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.
what if we have single element of target code this sequence will not worked
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
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!! :)
the approach is not valid for the array which contains negative elements.
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;
}
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;
}
if array is 1 1 1 1 2
and k=5
according to the code
this test case won't work
please if you know the give me a reply how to solve this......beacuse when if sum>k
while loop runs it will do sum-=a[i] i.e sum=5
now my sum =5
and j is incremented to 5 means aray size .....so this case wont work for the given code
need to apply one more condition
while(sum>k){
sum-=nums[i];
i++;
if(sum==k) //calculation ...;
}
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