title
Longest Subarray with sum K | Brute - Better - Optimal | Generate Subarrays

description
Notes/C++/Java/Python codes: Longest Subarray with sum K [positives]: https://takeuforward.org/data-structure/longest-subarray-with-given-sum-k/ Longest Subarray with sum K [positives + negatives]: https://takeuforward.org/arrays/longest-subarray-with-sum-k-postives-and-negatives/ Problem links. Longest Subarray with sum K [positives]: https://bit.ly/3GHyBOS Longest Subarray with sum K [positives + negatives]: http://bit.ly/3mNSZ9u We have solved the above problems, and we have gone from brute force and ended with the most optimal solution. Full Course: https://bit.ly/tufA2ZYt You can follow me across social media, all my handles are below: Linkedin/Instagram/Telegram: https://linktr.ee/takeUforward 0:00 Introduction of course

detail
{'title': 'Longest Subarray with sum K | Brute - Better - Optimal | Generate Subarrays', 'heatmap': [{'end': 501.459, 'start': 448.749, 'weight': 0.8}, {'end': 655.948, 'start': 621.741, 'weight': 0.789}, {'end': 1102.578, 'start': 950.031, 'weight': 0.837}, {'end': 1151.487, 'start': 1125.133, 'weight': 0.851}, {'end': 1334.434, 'start': 1221.178, 'weight': 0.944}, {'end': 1627.632, 'start': 1569.524, 'weight': 0.737}, {'end': 2278.671, 'start': 2250.618, 'weight': 0.724}], 'summary': 'The strybers a2z dsa course offers 456 modules and over 400 problem solutions, ensuring proficiency in ds algorithms for global companies. the video covers finding the longest subarray with a given sum, discussing brute force and optimized solutions, and addressing array summation, maximum length subarray, and hash map optimization.', 'chapters': [{'end': 44.687, 'segs': [{'end': 44.687, 'src': 'embed', 'start': 3.117, 'weight': 0, 'content': [{'end': 4.297, 'text': 'Hey everyone, welcome back to the channel.', 'start': 3.117, 'duration': 1.18}, {'end': 5.738, 'text': 'I hope you guys are doing extremely well.', 'start': 4.317, 'duration': 1.421}, {'end': 9.238, 'text': 'So this is another video from the Strybers A2Z DSA course.', 'start': 6.098, 'duration': 3.14}, {'end': 13.879, 'text': "Just in case here for the first time here, this is world's most in-depth course in DS Algo.", 'start': 9.718, 'duration': 4.161}, {'end': 18.2, 'text': 'Why do I say that? This course alone has 456 modules.', 'start': 14.219, 'duration': 3.981}, {'end': 22.421, 'text': 'When we end the course, we would have solved over 400 plus problems.', 'start': 18.6, 'duration': 3.821}, {'end': 25.542, 'text': 'You can go over the entire internet, you can buy any of the paid courses.', 'start': 22.781, 'duration': 2.761}, {'end': 28.702, 'text': 'None of them will be covering DS Algo in such depth.', 'start': 25.942, 'duration': 2.76}, {'end': 31.483, 'text': 'So one thing that I can give you as a guarantee is.', 'start': 29.002, 'duration': 2.481}, {'end': 39.606, 'text': 'if you complete this course, you can actually clear DS algorithms of any of the companies in any portion of the world.', 'start': 32.023, 'duration': 7.583}, {'end': 44.687, 'text': 'so till now we have covered till step 3.1 this problem.', 'start': 39.606, 'duration': 5.081}], 'summary': 'Strybers a2z dsa course has 456 modules and covers 400+ problems, offering the most in-depth ds algo course.', 'duration': 41.57, 'max_score': 3.117, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU3117.jpg'}], 'start': 3.117, 'title': 'The strybers a2z dsa course', 'summary': 'Highlights the depth of the strybers a2z dsa course, offering 456 modules and over 400 problem solutions, providing a guarantee to clear ds algorithms of any company globally.', 'chapters': [{'end': 44.687, 'start': 3.117, 'title': 'Strybers a2z dsa course', 'summary': 'Highlights the depth of the strybers a2z dsa course, offering 456 modules and over 400 problem solutions, providing a guarantee to clear ds algorithms of any company globally.', 'duration': 41.57, 'highlights': ['The course alone has 456 modules.', 'Over 400 plus problems will be solved by the end of the course.', 'Completing this course provides the guarantee to clear DS algorithms of any company globally.', 'Till now, the course has covered till step 3.1 problem.']}], 'duration': 41.57, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU3117.jpg', 'highlights': ['The course alone has 456 modules.', 'Over 400 plus problems will be solved by the end of the course.', 'Completing this course provides the guarantee to clear DS algorithms of any company globally.', 'Till now, the course has covered till step 3.1 problem.']}, {'end': 555.63, 'segs': [{'end': 94.005, 'src': 'embed', 'start': 65.414, 'weight': 1, 'content': [{'end': 71.716, 'text': "So the first question that might be coming up to your mind is, but what is the meaning of subarray? We haven't heard about this before.", 'start': 65.414, 'duration': 6.302}, {'end': 74.396, 'text': 'So just keep this in your mind.', 'start': 72.136, 'duration': 2.26}, {'end': 85.219, 'text': 'When I say subarray, it means contiguous, very, very important word, contiguous part of the array, contiguous part of the array.', 'start': 74.796, 'duration': 10.423}, {'end': 91.924, 'text': 'So I can say that this in itself is an array of 1.', 'start': 85.999, 'duration': 5.925}, {'end': 94.005, 'text': "So that's a subarray, a part of the array.", 'start': 91.924, 'duration': 2.081}], 'summary': 'Subarray is a contiguous part of an array.', 'duration': 28.591, 'max_score': 65.414, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU65414.jpg'}, {'end': 205.23, 'src': 'embed', 'start': 176.036, 'weight': 2, 'content': [{'end': 178.877, 'text': 'Because that is what they are looking for, and the summation is also 3..', 'start': 176.036, 'duration': 2.841}, {'end': 181.078, 'text': 'But the length of the savare is 1.', 'start': 178.877, 'duration': 2.201}, {'end': 185.12, 'text': 'And what they are asking is, give me the longest, give me the longest.', 'start': 181.078, 'duration': 4.042}, {'end': 190.502, 'text': 'So, if I take this, the summation is 3 and the length is 3 as well.', 'start': 186, 'duration': 4.502}, {'end': 194.364, 'text': 'The summation matches and the length is the longest.', 'start': 190.982, 'duration': 3.382}, {'end': 197.725, 'text': 'You cannot have a longer length than 3.', 'start': 194.824, 'duration': 2.901}, {'end': 200.347, 'text': 'Yeah, this is also a subarray with length three.', 'start': 197.725, 'duration': 2.622}, {'end': 203.109, 'text': "So there are two, but they're not asking you the count.", 'start': 200.667, 'duration': 2.442}, {'end': 205.23, 'text': 'That problem we will do in the future.', 'start': 203.629, 'duration': 1.601}], 'summary': 'The longest subarray with a summation of 3 has a length of 3.', 'duration': 29.194, 'max_score': 176.036, 'thumbnail': ''}, {'end': 353.038, 'src': 'embed', 'start': 323.277, 'weight': 4, 'content': [{'end': 324.838, 'text': 'So do I see a pattern? I do.', 'start': 323.277, 'duration': 1.561}, {'end': 334.447, 'text': 'Every time, if I keep a pointer i here, then I can just take a pointer j and the j will always start from i.', 'start': 326.58, 'duration': 7.867}, {'end': 337.59, 'text': 'And then what I can do is, I can say the subarray is from i to j.', 'start': 334.447, 'duration': 3.143}, {'end': 341.882, 'text': 'Do you see the first time? j is here, i is here.', 'start': 339.138, 'duration': 2.744}, {'end': 343.004, 'text': 'So the subarray is here.', 'start': 342.042, 'duration': 0.962}, {'end': 345.507, 'text': 'Then what I do is, I move j.', 'start': 343.344, 'duration': 2.163}, {'end': 347.59, 'text': 'Can I say the subarray is from i to j now? Yes.', 'start': 345.507, 'duration': 2.083}, {'end': 349.954, 'text': 'And then again I do, I move j.', 'start': 348.111, 'duration': 1.843}, {'end': 353.038, 'text': 'And can I say the subarray is from i to j? And then again I do, I move j.', 'start': 349.954, 'duration': 3.084}], 'summary': 'A pattern is observed where a pointer i and j define subarrays as j moves from i.', 'duration': 29.761, 'max_score': 323.277, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU323277.jpg'}, {'end': 501.459, 'src': 'heatmap', 'start': 428.362, 'weight': 5, 'content': [{'end': 435.044, 'text': 'this is this is how it will look if i have to generate all the summaries.', 'start': 428.362, 'duration': 6.682}, {'end': 437.184, 'text': 'and where is the summary from i to j?', 'start': 435.044, 'duration': 2.14}, {'end': 438.584, 'text': 'where is the summary from i to j?', 'start': 437.184, 'duration': 1.4}, {'end': 441.945, 'text': 'is it because if j is here, i is here.', 'start': 438.584, 'duration': 3.361}, {'end': 448.228, 'text': "Can I say the subarray is this? How do you find the summation of this subarray? It's easy.", 'start': 442.486, 'duration': 5.742}, {'end': 452.431, 'text': 'If the subarray is from i to j, run a loop na, run a loop.', 'start': 448.749, 'duration': 3.682}, {'end': 462.656, 'text': "So I'll say, okay, k is equal to i and it can run till j and the summation can be zero and summation plus equal to array of k.", 'start': 452.971, 'duration': 9.685}, {'end': 466.458, 'text': 'This way, I can submit the entire subarray from i to j.', 'start': 462.656, 'duration': 3.802}, {'end': 469.279, 'text': 'In this way, I can submit the entire subarray from i to j.', 'start': 466.458, 'duration': 2.821}, {'end': 474.337, 'text': 'Now what was required? longest equivalent to k.', 'start': 469.279, 'duration': 5.058}, {'end': 476.279, 'text': 'So, equivalent to k.', 'start': 474.337, 'duration': 1.942}, {'end': 477.18, 'text': "Let's write that condition.", 'start': 476.279, 'duration': 0.901}, {'end': 485.849, 'text': 'If s is equivalent to k, then the length and maybe you can keep the longest length as 0.', 'start': 477.901, 'duration': 7.948}, {'end': 488.691, 'text': 'So, the length will be max of the previous length.', 'start': 485.849, 'duration': 2.842}, {'end': 497.277, 'text': 'Comma, what is the length between i and j? What is the length between i and j? Imagine i is here and j is here.', 'start': 489.372, 'duration': 7.905}, {'end': 498.798, 'text': "What's the length? 2.", 'start': 497.357, 'duration': 1.441}, {'end': 501.459, 'text': "So that's j minus i plus 1.", 'start': 498.798, 'duration': 2.661}], 'summary': 'Algorithm to find summation of subarrays and longest equivalent to k.', 'duration': 24.069, 'max_score': 428.362, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU428362.jpg'}, {'end': 533.955, 'src': 'embed', 'start': 505.682, 'weight': 0, 'content': [{'end': 509.444, 'text': 'And eventually, wherever there is an equality, we take the longest.', 'start': 505.682, 'duration': 3.762}, {'end': 514.687, 'text': 'And right at the end, we can print the answer as length.', 'start': 510.004, 'duration': 4.683}, {'end': 519.385, 'text': 'Done What is the time complexity? Three loops.', 'start': 515.767, 'duration': 3.618}, {'end': 521.787, 'text': 'Somewhere near about we go off NQ.', 'start': 519.966, 'duration': 1.821}, {'end': 522.668, 'text': 'Near about.', 'start': 522.187, 'duration': 0.481}, {'end': 523.668, 'text': 'Not exactly.', 'start': 523.028, 'duration': 0.64}, {'end': 527.371, 'text': 'Why? Because this loop is diminishing.', 'start': 523.768, 'duration': 3.603}, {'end': 529.692, 'text': 'This also will reduce.', 'start': 527.391, 'duration': 2.301}, {'end': 532.094, 'text': 'So I can say somewhere around NQ.', 'start': 530.072, 'duration': 2.022}, {'end': 533.074, 'text': 'Not exactly.', 'start': 532.474, 'duration': 0.6}, {'end': 533.955, 'text': 'Not exactly.', 'start': 533.415, 'duration': 0.54}], 'summary': 'Time complexity: o(n^3) with diminishing loops.', 'duration': 28.273, 'max_score': 505.682, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU505682.jpg'}], 'start': 44.687, 'title': 'Finding longest subarray with given sum', 'summary': 'Covers the definition of a subarray, its significance, and the process of finding the longest subarray with a given sum, exemplifying with a summation of 3 and highlighting the importance of contiguous portions. it also discusses the brute force approach to find the longest subarray sum, iterating through all possible subarrays using three nested loops, leading to a time complexity of approximately o(n^3).', 'chapters': [{'end': 219.26, 'start': 44.687, 'title': 'Longest subarray with given sum', 'summary': 'Covers the definition of a subarray, its significance, and the process of finding the longest subarray with a given sum, exemplifying with a summation of 3 and highlighting the importance of contiguous portions.', 'duration': 174.573, 'highlights': ['The key definition of a subarray is provided, emphasizing its contiguous nature and depicting examples such as 1, 1, 1 and 4, 2, 3.', 'Illustration is given with the summation of 3, showcasing subarrays of different lengths and emphasizing the significance of finding the longest subarray with the given sum.', 'The importance of returning the length of the longest subarray is emphasized, with the example highlighting a subarray of length three with a summation of 3.']}, {'end': 555.63, 'start': 219.44, 'title': 'Brute force subarray sum', 'summary': 'Discusses the brute force approach to find the longest subarray sum, iterating through all possible subarrays using three nested loops, leading to a time complexity of approximately o(n^3).', 'duration': 336.19, 'highlights': ['The brute force approach involves iterating through all possible subarrays using three nested loops, leading to a time complexity of approximately O(N^3).', 'The subarray generation pattern involves extending by 1, with pointers i and j moving to create subarrays from i to j, leading to the observation of the subarray and summation of the subarray.', 'The summation of the entire subarray from i to j is found using a loop, and the longest subarray sum is determined using the length of the subarray.']}], 'duration': 510.943, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU44687.jpg', 'highlights': ['The brute force approach involves iterating through all possible subarrays using three nested loops, leading to a time complexity of approximately O(N^3)', 'The key definition of a subarray is provided, emphasizing its contiguous nature and depicting examples such as 1, 1, 1 and 4, 2, 3', 'Illustration is given with the summation of 3, showcasing subarrays of different lengths and emphasizing the significance of finding the longest subarray with the given sum', 'The importance of returning the length of the longest subarray is emphasized, with the example highlighting a subarray of length three with a summation of 3', 'The subarray generation pattern involves extending by 1, with pointers i and j moving to create subarrays from i to j, leading to the observation of the subarray and summation of the subarray', 'The summation of the entire subarray from i to j is found using a loop, and the longest subarray sum is determined using the length of the subarray']}, {'end': 939.473, 'segs': [{'end': 621.301, 'src': 'embed', 'start': 591.309, 'weight': 0, 'content': [{'end': 594.33, 'text': 'Then in the next subarray, we know the summation will be 2.', 'start': 591.309, 'duration': 3.021}, {'end': 595.631, 'text': 'Only one new element came up.', 'start': 594.33, 'duration': 1.301}, {'end': 597.211, 'text': 'So just add the one new element.', 'start': 595.811, 'duration': 1.4}, {'end': 599.051, 'text': 'Then again, one new element come up.', 'start': 597.811, 'duration': 1.24}, {'end': 600.372, 'text': 'So add the one new element.', 'start': 599.232, 'duration': 1.14}, {'end': 602.112, 'text': 'And again, one new element come up.', 'start': 600.652, 'duration': 1.46}, {'end': 603.153, 'text': 'Add the one new element.', 'start': 602.172, 'duration': 0.981}, {'end': 605, 'text': 'And get the summation 7.', 'start': 603.293, 'duration': 1.707}, {'end': 609.182, 'text': 'Do I need to iterate in the entire subarray? We do not.', 'start': 605, 'duration': 4.182}, {'end': 614.525, 'text': 'Because when the j is moving, when the j is moving, I just keep on, keep on adding, keep on adding.', 'start': 609.762, 'duration': 4.763}, {'end': 615.505, 'text': 'Quite simple.', 'start': 615.005, 'duration': 0.5}, {'end': 621.301, 'text': "So what I'll say is, Let's keep the s as 0, and every time j moves, I'll just add it.", 'start': 615.926, 'duration': 5.375}], 'summary': 'Summation of elements results in 7 without iterating through the entire subarray.', 'duration': 29.992, 'max_score': 591.309, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU591309.jpg'}, {'end': 655.948, 'src': 'heatmap', 'start': 621.741, 'weight': 0.789, 'content': [{'end': 625.845, 'text': 'What will be the value for the first time? If i is here, first time 2 will be added.', 'start': 621.741, 'duration': 4.104}, {'end': 627.827, 'text': 'Then j will move here, then 3 will be added.', 'start': 626.245, 'duration': 1.582}, {'end': 629.548, 'text': 'Then j will move here, 1 will be added.', 'start': 628.087, 'duration': 1.461}, {'end': 631.77, 'text': 'And eventually everything will be in s.', 'start': 629.949, 'duration': 1.821}, {'end': 632.811, 'text': 'And you can easily compare.', 'start': 631.77, 'duration': 1.041}, {'end': 638.276, 'text': 'If I do this, the brute force boils down to somewhere near about n squared.', 'start': 633.271, 'duration': 5.005}, {'end': 641.718, 'text': 'with a space complexity of b go of 1.', 'start': 638.976, 'duration': 2.742}, {'end': 647.862, 'text': "So this is what you'll tell the interviewer that the brute force that I can do is b go of n square at the best case.", 'start': 641.718, 'duration': 6.144}, {'end': 653.286, 'text': "So obviously the interviewer will not be happy with the brute force solution and he'll ask you to optimize it.", 'start': 648.503, 'duration': 4.783}, {'end': 655.948, 'text': "And that's when you will come up with the better solution.", 'start': 653.566, 'duration': 2.382}], 'summary': 'Brute force solution has time complexity of n squared and space complexity of 1, interviewer will expect an optimized solution.', 'duration': 34.207, 'max_score': 621.741, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU621741.jpg'}, {'end': 841.013, 'src': 'embed', 'start': 769.75, 'weight': 2, 'content': [{'end': 774.851, 'text': "There are five subarrays with the dot element as the last and that's what my focus will be.", 'start': 769.75, 'duration': 5.101}, {'end': 797.14, 'text': "So can I say if there exists, I'll write this, if there exists a subarray with summation k as dot as the last element, dot as the last element.", 'start': 776.127, 'duration': 21.013}, {'end': 804.785, 'text': 'So hypothetically imagine these three numbers give you the summation of k, hypothetically.', 'start': 798.461, 'duration': 6.324}, {'end': 809.39, 'text': 'Probably there exists a subarray who has a summation of k.', 'start': 805.646, 'duration': 3.744}, {'end': 815.897, 'text': 'But you cannot have this sum of some middle subarray in between.', 'start': 809.39, 'duration': 6.507}, {'end': 822.884, 'text': 'But can you do reverse engineering? And can I say, wait, probably there is a subarray.', 'start': 816.418, 'duration': 6.466}, {'end': 825.047, 'text': 'Probably there is a subarray with a summation of k.', 'start': 823.005, 'duration': 2.042}, {'end': 830.55, 'text': 'So if there is a summation of k, what will be the summation of this? Reverse mathematics.', 'start': 826.089, 'duration': 4.461}, {'end': 840.813, 'text': 'If the entire is x, if this is k, can I say this will be x minus k? x minus k.', 'start': 831.13, 'duration': 9.683}, {'end': 841.013, 'text': 'I can.', 'start': 840.813, 'duration': 0.2}], 'summary': 'Focus on finding subarrays with summation k as the last element, using reverse engineering to calculate x minus k.', 'duration': 71.263, 'max_score': 769.75, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU769750.jpg'}], 'start': 557.412, 'title': 'Optimizing subarray summation', 'summary': 'Discusses optimizing subarray summation using hashing to improve from o(n^2) to a more efficient solution. it also covers the concept of finding subarrays with a sum k using reverse mathematics and the use of hash maps for efficient computation.', 'chapters': [{'end': 666.436, 'start': 557.412, 'title': 'Subarray summation optimization', 'summary': 'Discusses optimizing subarray summation using hashing to improve from a brute force complexity of o(n^2) to a more efficient solution.', 'duration': 109.024, 'highlights': ['The brute force solution for subarray summation has a complexity of O(n^2) with a space complexity of O(1), which can be optimized using hashing.', 'Using hashing to optimize subarray summation reduces the time complexity from O(n^2) to a more efficient solution.']}, {'end': 939.473, 'start': 667.196, 'title': 'Subarray sum with reverse mathematics', 'summary': 'Discusses the concept of finding subarrays with a sum k using reverse mathematics, explaining the key steps to identify subarrays with k as the last element and the use of hash maps for efficient computation.', 'duration': 272.277, 'highlights': ['The chapter explains the process of finding subarrays with a sum k using reverse mathematics and prefix sums.', 'The speaker emphasizes the identification of subarrays with k as the last element using reverse mathematics.', 'The concept of using hash maps to efficiently compute subarrays with a sum k is discussed.']}], 'duration': 382.061, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU557412.jpg', 'highlights': ['Using hashing to optimize subarray summation reduces time complexity from O(n^2) to a more efficient solution.', 'The brute force solution for subarray summation has a complexity of O(n^2) and can be optimized using hashing.', 'The chapter explains the process of finding subarrays with a sum k using reverse mathematics and prefix sums.', 'The concept of using hash maps to efficiently compute subarrays with a sum k is discussed.', 'The speaker emphasizes the identification of subarrays with k as the last element using reverse mathematics.']}, {'end': 1158.191, 'segs': [{'end': 1102.578, 'src': 'heatmap', 'start': 939.933, 'weight': 0, 'content': [{'end': 941.214, 'text': 'Did not understand, not an issue.', 'start': 939.933, 'duration': 1.281}, {'end': 942.054, 'text': "Let's do the dry run.", 'start': 941.334, 'duration': 0.72}, {'end': 949.258, 'text': "So we will be at the first element and we'll do a summation zero and initially no subarrays are found, so then zero.", 'start': 942.894, 'duration': 6.364}, {'end': 952.355, 'text': 'First element one, increase the summation to one.', 'start': 950.031, 'duration': 2.324}, {'end': 956.241, 'text': "The summation is one and that's not equivalent to three.", 'start': 952.675, 'duration': 3.566}, {'end': 960.968, 'text': 'So you take one and you say it occurred at index zero.', 'start': 956.801, 'duration': 4.167}, {'end': 963.071, 'text': "Probably I'll write the index for better understanding.", 'start': 961.168, 'duration': 1.903}, {'end': 968.884, 'text': 'So, 1 occurred at index 0.', 'start': 964.983, 'duration': 3.901}, {'end': 978.227, 'text': 'Next, move the pointer to summation increases to 3, summation increases to 3, which is equivalent to k, which is equivalent to k.', 'start': 968.884, 'duration': 9.343}, {'end': 986.649, 'text': 'So, what do you say is, okay, wait, this entire prefix sum, this entire prefix sum is equivalent to the k.', 'start': 978.227, 'duration': 8.422}, {'end': 991.79, 'text': 'That means this in itself is an array or a subarray who is giving me the sum.', 'start': 986.649, 'duration': 5.141}, {'end': 996.816, 'text': 'So, if the subarray is equivalent till index 1.', 'start': 992.251, 'duration': 4.565}, {'end': 998.938, 'text': 'So the length will be 2.', 'start': 996.816, 'duration': 2.122}, {'end': 1000.58, 'text': 'Zero based indexing, so the length will be 2.', 'start': 998.938, 'duration': 1.642}, {'end': 1007.326, 'text': 'Perfect And at the same time, say you got 3 till here, which is index 1.', 'start': 1000.58, 'duration': 6.746}, {'end': 1008.106, 'text': "Perfect Let's move.", 'start': 1007.326, 'duration': 0.78}, {'end': 1009.628, 'text': 'You got 3 now.', 'start': 1009.047, 'duration': 0.581}, {'end': 1011.269, 'text': 'You got 3.', 'start': 1009.988, 'duration': 1.281}, {'end': 1012.79, 'text': 'The summation will be 6.', 'start': 1011.269, 'duration': 1.521}, {'end': 1014.59, 'text': 'The prefix summation is 6.', 'start': 1012.79, 'duration': 1.8}, {'end': 1016.931, 'text': 'The prefix summation is 6.', 'start': 1014.59, 'duration': 2.341}, {'end': 1018.872, 'text': 'Now comes the twist.', 'start': 1016.931, 'duration': 1.941}, {'end': 1020.913, 'text': 'So, 3 elements.', 'start': 1019.512, 'duration': 1.401}, {'end': 1024.294, 'text': 'And till now the prefix sum is 6.', 'start': 1022.153, 'duration': 2.141}, {'end': 1026.515, 'text': 'And you are looking for someone with 3.', 'start': 1024.294, 'duration': 2.221}, {'end': 1027.876, 'text': 'And that someone is this.', 'start': 1026.515, 'duration': 1.361}, {'end': 1030.757, 'text': 'So if this is 3, I did a reverse engineering.', 'start': 1028.316, 'duration': 2.441}, {'end': 1032.657, 'text': 'The remaining was 3.', 'start': 1031.117, 'duration': 1.54}, {'end': 1033.718, 'text': 'I said, hey wait.', 'start': 1032.657, 'duration': 1.061}, {'end': 1036.319, 'text': 'Did we get some 3 before? And he says, yes.', 'start': 1034.318, 'duration': 2.001}, {'end': 1038.859, 'text': 'Till index 1 you got a 3.', 'start': 1036.858, 'duration': 2.001}, {'end': 1043.383, 'text': 'That means there does exist a subarray with a k.', 'start': 1038.859, 'duration': 4.524}, {'end': 1047.386, 'text': "Reverse So what I'll do is I'll say till here it is 6.", 'start': 1043.383, 'duration': 4.003}, {'end': 1048.727, 'text': 'You need 3.', 'start': 1047.386, 'duration': 1.341}, {'end': 1049.967, 'text': '6 minus 3 is 3.', 'start': 1048.727, 'duration': 1.24}, {'end': 1050.808, 'text': 'Look from the front.', 'start': 1049.967, 'duration': 0.841}, {'end': 1053.37, 'text': 'Is there a 3? He says till 1 there is 3.', 'start': 1051.128, 'duration': 2.242}, {'end': 1054.751, 'text': 'Till 1 there is a 3.', 'start': 1053.37, 'duration': 1.381}, {'end': 1055.611, 'text': "I'm getting a subarray.", 'start': 1054.751, 'duration': 0.86}, {'end': 1056.772, 'text': "I'm getting a subarray.", 'start': 1056.011, 'duration': 0.761}, {'end': 1058.493, 'text': "You're standing at 2.", 'start': 1057.112, 'duration': 1.381}, {'end': 1059.894, 'text': 'Till 1 there is a 3.', 'start': 1058.493, 'duration': 1.401}, {'end': 1061.035, 'text': 'So 2 minus 1.', 'start': 1059.894, 'duration': 1.141}, {'end': 1063.637, 'text': 'So the length of that subarray is 1.', 'start': 1061.035, 'duration': 2.602}, {'end': 1065.978, 'text': 'The length of that subarray is 1.', 'start': 1063.637, 'duration': 2.341}, {'end': 1066.999, 'text': "But that's not greater than 2.", 'start': 1065.978, 'duration': 1.021}, {'end': 1067.919, 'text': "So you'll not do anything.", 'start': 1066.999, 'duration': 0.92}, {'end': 1070.902, 'text': '6 comma 2.', 'start': 1069.901, 'duration': 1.001}, {'end': 1072.523, 'text': "Perfect Let's go.", 'start': 1070.902, 'duration': 1.621}, {'end': 1074.085, 'text': 'You got 1.', 'start': 1072.543, 'duration': 1.542}, {'end': 1075.186, 'text': '7 is the new sum.', 'start': 1074.085, 'duration': 1.101}, {'end': 1078.229, 'text': 'So what can I say? I have 4 elements.', 'start': 1075.826, 'duration': 2.403}, {'end': 1081.504, 'text': 'And the prefix sum of this is 7.', 'start': 1079.383, 'duration': 2.121}, {'end': 1082.985, 'text': 'What am I looking for? 3.', 'start': 1081.504, 'duration': 1.481}, {'end': 1086.288, 'text': 'For someone to be 3, someone from the start has to be 4.', 'start': 1082.985, 'duration': 3.303}, {'end': 1088.329, 'text': 'Do we have someone from the start as 4? No.', 'start': 1086.288, 'duration': 2.041}, {'end': 1089.99, 'text': 'So did not find.', 'start': 1089.089, 'duration': 0.901}, {'end': 1092.972, 'text': 'Take the 7 and put it at index.', 'start': 1090.31, 'duration': 2.662}, {'end': 1094.153, 'text': 'How much is that? 3.', 'start': 1093.072, 'duration': 1.081}, {'end': 1095.834, 'text': "Perfect And now let's move.", 'start': 1094.153, 'duration': 1.681}, {'end': 1099.556, 'text': 'So when you move ahead, you get 8.', 'start': 1096.574, 'duration': 2.982}, {'end': 1102.578, 'text': "So when you're getting 8, which means you're having 5 elements.", 'start': 1099.556, 'duration': 3.022}], 'summary': 'Explaining the process of finding subarrays with a specific sum using prefix summation and reverse engineering.', 'duration': 86.582, 'max_score': 939.933, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU939933.jpg'}, {'end': 1105.641, 'src': 'embed', 'start': 1053.37, 'weight': 5, 'content': [{'end': 1054.751, 'text': 'Till 1 there is a 3.', 'start': 1053.37, 'duration': 1.381}, {'end': 1055.611, 'text': "I'm getting a subarray.", 'start': 1054.751, 'duration': 0.86}, {'end': 1056.772, 'text': "I'm getting a subarray.", 'start': 1056.011, 'duration': 0.761}, {'end': 1058.493, 'text': "You're standing at 2.", 'start': 1057.112, 'duration': 1.381}, {'end': 1059.894, 'text': 'Till 1 there is a 3.', 'start': 1058.493, 'duration': 1.401}, {'end': 1061.035, 'text': 'So 2 minus 1.', 'start': 1059.894, 'duration': 1.141}, {'end': 1063.637, 'text': 'So the length of that subarray is 1.', 'start': 1061.035, 'duration': 2.602}, {'end': 1065.978, 'text': 'The length of that subarray is 1.', 'start': 1063.637, 'duration': 2.341}, {'end': 1066.999, 'text': "But that's not greater than 2.", 'start': 1065.978, 'duration': 1.021}, {'end': 1067.919, 'text': "So you'll not do anything.", 'start': 1066.999, 'duration': 0.92}, {'end': 1070.902, 'text': '6 comma 2.', 'start': 1069.901, 'duration': 1.001}, {'end': 1072.523, 'text': "Perfect Let's go.", 'start': 1070.902, 'duration': 1.621}, {'end': 1074.085, 'text': 'You got 1.', 'start': 1072.543, 'duration': 1.542}, {'end': 1075.186, 'text': '7 is the new sum.', 'start': 1074.085, 'duration': 1.101}, {'end': 1078.229, 'text': 'So what can I say? I have 4 elements.', 'start': 1075.826, 'duration': 2.403}, {'end': 1081.504, 'text': 'And the prefix sum of this is 7.', 'start': 1079.383, 'duration': 2.121}, {'end': 1082.985, 'text': 'What am I looking for? 3.', 'start': 1081.504, 'duration': 1.481}, {'end': 1086.288, 'text': 'For someone to be 3, someone from the start has to be 4.', 'start': 1082.985, 'duration': 3.303}, {'end': 1088.329, 'text': 'Do we have someone from the start as 4? No.', 'start': 1086.288, 'duration': 2.041}, {'end': 1089.99, 'text': 'So did not find.', 'start': 1089.089, 'duration': 0.901}, {'end': 1092.972, 'text': 'Take the 7 and put it at index.', 'start': 1090.31, 'duration': 2.662}, {'end': 1094.153, 'text': 'How much is that? 3.', 'start': 1093.072, 'duration': 1.081}, {'end': 1095.834, 'text': "Perfect And now let's move.", 'start': 1094.153, 'duration': 1.681}, {'end': 1099.556, 'text': 'So when you move ahead, you get 8.', 'start': 1096.574, 'duration': 2.982}, {'end': 1102.578, 'text': "So when you're getting 8, which means you're having 5 elements.", 'start': 1099.556, 'duration': 3.022}, {'end': 1104.18, 'text': "And again, right? You're having 5 elements.", 'start': 1102.739, 'duration': 1.441}, {'end': 1105.641, 'text': 'It is having 8.', 'start': 1104.54, 'duration': 1.101}], 'summary': 'Finding subarrays and updating sums with prefix sums.', 'duration': 52.271, 'max_score': 1053.37, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU1053370.jpg'}, {'end': 1154.969, 'src': 'heatmap', 'start': 1125.133, 'weight': 0.851, 'content': [{'end': 1126.414, 'text': '6 elements are giving you a summation.', 'start': 1125.133, 'duration': 1.281}, {'end': 1135.317, 'text': 'So for someone to be three, someone has to be six and I get a six, I get a six at index two adding.', 'start': 1127.352, 'duration': 7.965}, {'end': 1136.778, 'text': 'So this is six.', 'start': 1135.377, 'duration': 1.401}, {'end': 1139.179, 'text': 'So these many remaining will be three.', 'start': 1137.318, 'duration': 1.861}, {'end': 1142.221, 'text': "So you're currently at five till two there was three.", 'start': 1139.7, 'duration': 2.521}, {'end': 1144.703, 'text': 'So the subtraction, the length is three.', 'start': 1142.701, 'duration': 2.002}, {'end': 1147.605, 'text': 'So you want a better one.', 'start': 1145.223, 'duration': 2.382}, {'end': 1151.487, 'text': 'So this is how you can go ahead and you can figure out if someone was there in the back.', 'start': 1147.965, 'duration': 3.522}, {'end': 1154.969, 'text': 'This is what I will call as a better solution.', 'start': 1151.947, 'duration': 3.022}], 'summary': 'The process involves summation, subtraction, and finding a better solution.', 'duration': 29.836, 'max_score': 1125.133, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU1125133.jpg'}], 'start': 939.933, 'title': 'Finding subarrays', 'summary': 'Explains the process of finding subarrays in a sequence, including the method for finding subarrays whose sum is equal to a given value and analyzing the prefix sum. it provides a detailed example and discusses determining the length and indexes of subarrays.', 'chapters': [{'end': 1026.515, 'start': 939.933, 'title': 'Subarray sum equals k', 'summary': 'Explains the process of finding subarrays whose sum is equal to a given value, using a detailed example and explaining the length and indexes of the subarrays.', 'duration': 86.582, 'highlights': ['The process involves iterating through the array and maintaining a running sum, checking for subarrays with a specific sum. For example, when the prefix sum is equivalent to the given value k, a subarray is found, and its length and indexes are determined.', 'The chapter also emphasizes the importance of zero-based indexing when calculating the length and indexes of the subarrays. For instance, the length of the subarray is determined based on zero-based indexing.', 'The detailed example illustrates the step-by-step process of finding subarrays with the given sum, providing a clear understanding of the algorithm and its application.']}, {'end': 1158.191, 'start': 1026.515, 'title': 'Finding subarrays', 'summary': 'Discusses a method of finding subarrays in a sequence, where certain conditions need to be met, and the process involves analyzing the prefix sum, checking for specific values, and determining the length of subarrays.', 'duration': 131.676, 'highlights': ['The process involves analyzing the prefix sum', 'Determining the length of subarrays', 'Checking for specific values']}], 'duration': 218.258, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU939933.jpg', 'highlights': ['The process involves iterating through the array and maintaining a running sum, checking for subarrays with a specific sum.', 'The detailed example illustrates the step-by-step process of finding subarrays with the given sum, providing a clear understanding of the algorithm and its application.', 'The chapter also emphasizes the importance of zero-based indexing when calculating the length and indexes of the subarrays.', 'The process involves analyzing the prefix sum', 'For example, when the prefix sum is equivalent to the given value k, a subarray is found, and its length and indexes are determined.', 'Determining the length of subarrays', 'Checking for specific values']}, {'end': 1506.501, 'segs': [{'end': 1186.829, 'src': 'embed', 'start': 1158.552, 'weight': 0, 'content': [{'end': 1164.175, 'text': "I'll be quoting this up because I want your quoting skills to work because this is a very important question.", 'start': 1158.552, 'duration': 5.623}, {'end': 1167.077, 'text': "So you're given the vector and you're given the cake.", 'start': 1164.215, 'duration': 2.862}, {'end': 1170.86, 'text': 'Something important to notice is it is given as long log.', 'start': 1167.317, 'duration': 3.543}, {'end': 1172.261, 'text': 'First, declare the map.', 'start': 1171.38, 'duration': 0.881}, {'end': 1177.044, 'text': 'So map will be long, long because that is where we will store the prefix sum.', 'start': 1172.761, 'duration': 4.283}, {'end': 1180.306, 'text': 'So you can say pre-map, pre-sum map or something like this.', 'start': 1177.344, 'duration': 2.962}, {'end': 1181.587, 'text': 'Perfect, done.', 'start': 1181.067, 'duration': 0.52}, {'end': 1186.829, 'text': "Now what I'll do is I'll go across the entire array, which is something like a dot size.", 'start': 1182.127, 'duration': 4.702}], 'summary': 'Given vector and cake, declare long-long map for prefix sum storage.', 'duration': 28.277, 'max_score': 1158.552, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU1158552.jpg'}, {'end': 1340.56, 'src': 'heatmap', 'start': 1208.279, 'weight': 4, 'content': [{'end': 1208.599, 'text': 'Over here.', 'start': 1208.279, 'duration': 0.32}, {'end': 1212.516, 'text': "I'll say sum plus equal to a of i.", 'start': 1208.599, 'duration': 3.917}, {'end': 1221.178, 'text': 'and remember initially always check if the array from start till the current index is giving you k.', 'start': 1212.516, 'duration': 8.662}, {'end': 1228.179, 'text': 'if it is giving you, then the max length will always be max of max length, comma i plus one.', 'start': 1221.178, 'duration': 7.001}, {'end': 1234.06, 'text': "it will always be like, even if you do not write max, it will work, because if you add i, that's always the maximum.", 'start': 1228.179, 'duration': 5.881}, {'end': 1236.521, 'text': "okay, if that's the case, that's perfect.", 'start': 1234.06, 'duration': 2.461}, {'end': 1240.504, 'text': "what can be the other case i'm looking for remaining.", 'start': 1236.521, 'duration': 3.983}, {'end': 1242.447, 'text': 'bring the reverse mathematics.', 'start': 1240.504, 'duration': 1.943}, {'end': 1243.808, 'text': 'how much do i require?', 'start': 1242.447, 'duration': 1.361}, {'end': 1245.471, 'text': 'this is what i require.', 'start': 1243.808, 'duration': 1.663}, {'end': 1251.759, 'text': 'so if my map has this remaining, which means it will not be pointing to the end.', 'start': 1245.471, 'duration': 6.288}, {'end': 1255.021, 'text': 'So remember, this is pre-sum map.', 'start': 1253.24, 'duration': 1.781}, {'end': 1258.004, 'text': 'So please write pre-sum map dot end.', 'start': 1255.362, 'duration': 2.642}, {'end': 1261.586, 'text': 'If it does exist, there means it does.', 'start': 1258.604, 'duration': 2.982}, {'end': 1269.853, 'text': 'So thereby, what will be the length of this sum array? Can I say the length of this will be i minus pre-sum map of the remaining wherever it is.', 'start': 1262.147, 'duration': 7.706}, {'end': 1275.397, 'text': 'And then you can do a say max length equal to max, max length, comma length.', 'start': 1270.293, 'duration': 5.104}, {'end': 1280.121, 'text': 'Right at the end of the day, whatever sum you have generated is a pre-sum map.', 'start': 1276.278, 'duration': 3.843}, {'end': 1281.902, 'text': 'This is a pre-sum map.', 'start': 1280.941, 'duration': 0.961}, {'end': 1295.754, 'text': 'of this particular sum is equal to i, something to ponder over here like this, if I try to submit this, this will run.', 'start': 1284.013, 'duration': 11.741}, {'end': 1298.895, 'text': "There's a slight edge case that I want to talk about.", 'start': 1296.714, 'duration': 2.181}, {'end': 1304.257, 'text': 'This code that we have written, is that correct? That is correct, but only for positives.', 'start': 1299.575, 'duration': 4.682}, {'end': 1309.798, 'text': 'If I tell you that the array has zeros, the code that you have written will be wrong.', 'start': 1304.757, 'duration': 5.041}, {'end': 1312.579, 'text': "Why? Let's understand that by an example.", 'start': 1310.438, 'duration': 2.141}, {'end': 1318.481, 'text': 'So imagine I take an array, which has something like two comma zero comma zero comma.', 'start': 1312.959, 'duration': 5.522}, {'end': 1322.044, 'text': '3 and looking for a summation of 3.', 'start': 1319.421, 'duration': 2.623}, {'end': 1323.685, 'text': "that's what i'm looking for.", 'start': 1322.044, 'duration': 1.641}, {'end': 1324.866, 'text': 'how does it work?', 'start': 1323.685, 'duration': 1.181}, {'end': 1325.747, 'text': "it's very simple.", 'start': 1324.866, 'duration': 0.881}, {'end': 1334.434, 'text': 'we take a prefix sum, we keep a pointer here, we have a hash man right and then we have a length as 0 initially and prefix sum as 0..', 'start': 1325.747, 'duration': 8.687}, {'end': 1340.56, 'text': "let's start the integration when we add 2 which is index 0 we We do the prefix sum as 2.", 'start': 1334.434, 'duration': 6.126}], 'summary': 'The transcript discusses the calculation of maximum subarray length based on given conditions.', 'duration': 132.281, 'max_score': 1208.279, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU1208279.jpg'}, {'end': 1312.579, 'src': 'embed', 'start': 1262.147, 'weight': 5, 'content': [{'end': 1269.853, 'text': 'So thereby, what will be the length of this sum array? Can I say the length of this will be i minus pre-sum map of the remaining wherever it is.', 'start': 1262.147, 'duration': 7.706}, {'end': 1275.397, 'text': 'And then you can do a say max length equal to max, max length, comma length.', 'start': 1270.293, 'duration': 5.104}, {'end': 1280.121, 'text': 'Right at the end of the day, whatever sum you have generated is a pre-sum map.', 'start': 1276.278, 'duration': 3.843}, {'end': 1281.902, 'text': 'This is a pre-sum map.', 'start': 1280.941, 'duration': 0.961}, {'end': 1295.754, 'text': 'of this particular sum is equal to i, something to ponder over here like this, if I try to submit this, this will run.', 'start': 1284.013, 'duration': 11.741}, {'end': 1298.895, 'text': "There's a slight edge case that I want to talk about.", 'start': 1296.714, 'duration': 2.181}, {'end': 1304.257, 'text': 'This code that we have written, is that correct? That is correct, but only for positives.', 'start': 1299.575, 'duration': 4.682}, {'end': 1309.798, 'text': 'If I tell you that the array has zeros, the code that you have written will be wrong.', 'start': 1304.757, 'duration': 5.041}, {'end': 1312.579, 'text': "Why? Let's understand that by an example.", 'start': 1310.438, 'duration': 2.141}], 'summary': 'Code calculates length of sum array using pre-sum map and handles edge case for zeros.', 'duration': 50.432, 'max_score': 1262.147, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU1262147.jpg'}, {'end': 1480.229, 'src': 'embed', 'start': 1420.105, 'weight': 1, 'content': [{'end': 1423.648, 'text': 'So thereby this much is the summary, which is again, correct.', 'start': 1420.105, 'duration': 3.543}, {'end': 1426.444, 'text': 'but we need longest.', 'start': 1424.824, 'duration': 1.62}, {'end': 1430.426, 'text': 'we do not need shortest, we do not need shortest, we need longest.', 'start': 1426.444, 'duration': 3.982}, {'end': 1433.607, 'text': 'so apparently we should have just stored.', 'start': 1430.426, 'duration': 3.181}, {'end': 1443.109, 'text': 'we should have just stored 2 for index 0, and this subarray 0, comma 0, comma 3 would have been the answer for longest.', 'start': 1433.607, 'duration': 9.502}, {'end': 1450.812, 'text': 'thereby, if a sum previously does exist, you should not re-update.', 'start': 1443.109, 'duration': 7.703}, {'end': 1461.439, 'text': "you should not re-update because because if there is something like this, and this one has a summation of x and you're looking for k,", 'start': 1450.812, 'duration': 10.627}, {'end': 1469.904, 'text': "you'll try to look as left as possible for x, minus k, you'll try to look as left as possible for x, minus k.", 'start': 1461.439, 'duration': 8.465}, {'end': 1470.705, 'text': 'did you get this?', 'start': 1469.904, 'duration': 0.801}, {'end': 1480.229, 'text': "i hope you did get this because you'll try to look for the leftmost guy, for the sum of two, because sum of two is here, here and here,", 'start': 1470.705, 'duration': 9.524}], 'summary': 'Storing 2 for index 0 yields the longest subarray 0, 0, 3.', 'duration': 60.124, 'max_score': 1420.105, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU1420105.jpg'}], 'start': 1158.552, 'title': 'Finding maximum length subarray', 'summary': 'Discusses the process of finding the maximum length of a subarray with a given sum, utilizing a map to store the prefix sum and iterating through the array to calculate the maximum length. it also highlights the importance of not re-updating the sum and looking for the leftmost element to obtain the longest summary.', 'chapters': [{'end': 1234.06, 'start': 1158.552, 'title': 'Finding maximum length subarray', 'summary': 'Discusses the process of finding the maximum length of a subarray with a given sum, utilizing a map to store the prefix sum and iterating through the array to calculate the maximum length.', 'duration': 75.508, 'highlights': ['The chapter emphasizes the importance of utilizing a map to store the prefix sum for efficient computation and retrieval of the required subarray length.', 'It explains the iterative process through the entire array to calculate the maximum length of the subarray by checking the sum from the start till the current index, and updating the maximum length accordingly.']}, {'end': 1312.579, 'start': 1234.06, 'title': 'Reverse mathematics and pre-sum mapping', 'summary': 'Discusses reverse mathematics and pre-sum mapping to calculate the length of a sum array, highlighting the potential issues with the code for arrays containing zeros.', 'duration': 78.519, 'highlights': ['The length of the sum array is calculated using the formula i minus pre-sum map of the remaining elements (wherever it is).', 'A slight edge case is highlighted where the code written for calculating the length of the sum array is incorrect for arrays containing zeros.', 'The code provided for calculating the length of the sum array is correct only for positive numbers.']}, {'end': 1506.501, 'start': 1312.959, 'title': 'Prefix sum and hash map algorithm', 'summary': 'Discusses the application of prefix sum and hash map in finding the longest subarray with a given sum, emphasizing the importance of not re-updating the sum and looking for the leftmost element to obtain the longest summary.', 'duration': 193.542, 'highlights': ['The algorithm involves using prefix sum and hash map to find the longest subarray with a given sum, where the importance of not re-updating the sum is emphasized.', 'Emphasizes the significance of looking for the leftmost element to obtain the longest summary, as it plays a crucial role in locating the desired sum.', 'Explains the necessity of storing values in the map and not re-updating them to ensure the retrieval of the longest subarray with the given sum.']}], 'duration': 347.949, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU1158552.jpg', 'highlights': ['The chapter emphasizes the importance of utilizing a map to store the prefix sum for efficient computation and retrieval of the required subarray length.', 'The algorithm involves using prefix sum and hash map to find the longest subarray with a given sum, where the importance of not re-updating the sum is emphasized.', 'Explains the necessity of storing values in the map and not re-updating them to ensure the retrieval of the longest subarray with the given sum.', 'Emphasizes the significance of looking for the leftmost element to obtain the longest summary, as it plays a crucial role in locating the desired sum.', 'It explains the iterative process through the entire array to calculate the maximum length of the subarray by checking the sum from the start till the current index, and updating the maximum length accordingly.', 'The length of the sum array is calculated using the formula i minus pre-sum map of the remaining elements (wherever it is).', 'The code provided for calculating the length of the sum array is correct only for positive numbers.', 'A slight edge case is highlighted where the code written for calculating the length of the sum array is incorrect for arrays containing zeros.']}, {'end': 1712.791, 'segs': [{'end': 1632.256, 'src': 'heatmap', 'start': 1562.002, 'weight': 0, 'content': [{'end': 1565.943, 'text': 'If you observe this particular code is partially accepted.', 'start': 1562.002, 'duration': 3.941}, {'end': 1569.224, 'text': 'Why? Because this was the better solution that we were discussing.', 'start': 1566.444, 'duration': 2.78}, {'end': 1581.497, 'text': 'We still need to optimize this, but this same code will work for a problem that has positives and negatives in the array,', 'start': 1569.524, 'duration': 11.973}, {'end': 1587.501, 'text': 'because in that case the better one for the positive and zeros is the optimal.', 'start': 1581.497, 'duration': 6.004}, {'end': 1594.286, 'text': 'You cannot optimize this code any further if the array has negatives, zeros, and positives.', 'start': 1587.942, 'duration': 6.344}, {'end': 1600.331, 'text': "So I'll just quickly go and submit this and you'll see that this is actually okay.", 'start': 1594.627, 'duration': 5.704}, {'end': 1601.832, 'text': 'So just change the name now.', 'start': 1600.411, 'duration': 1.421}, {'end': 1602.693, 'text': 'Okay, cool.', 'start': 1602.352, 'duration': 0.341}, {'end': 1609.518, 'text': "So you'll see that this is actually running for this particular problem and it will be completely accepted.", 'start': 1603.493, 'duration': 6.025}, {'end': 1615.262, 'text': 'Yes While over here, it was not because this is a better solution.', 'start': 1609.578, 'duration': 5.684}, {'end': 1619.386, 'text': "So let's discuss the time complexity and see if we can get an optimal or not.", 'start': 1615.563, 'duration': 3.823}, {'end': 1621.647, 'text': 'So we did code up the better solution.', 'start': 1619.606, 'duration': 2.041}, {'end': 1627.632, 'text': 'And if you saw that that better was an optimal one, if the array has positives as well as negatives.', 'start': 1621.767, 'duration': 5.865}, {'end': 1632.256, 'text': 'But if I ask you for the better solution, yes, what is the time complexity?', 'start': 1628.012, 'duration': 4.244}], 'summary': 'A partially accepted code was discussed, and a better solution optimized for positive and zero array problems was submitted, with time complexity being evaluated.', 'duration': 70.254, 'max_score': 1562.002, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU1562002.jpg'}, {'end': 1646.437, 'src': 'embed', 'start': 1615.563, 'weight': 2, 'content': [{'end': 1619.386, 'text': "So let's discuss the time complexity and see if we can get an optimal or not.", 'start': 1615.563, 'duration': 3.823}, {'end': 1621.647, 'text': 'So we did code up the better solution.', 'start': 1619.606, 'duration': 2.041}, {'end': 1627.632, 'text': 'And if you saw that that better was an optimal one, if the array has positives as well as negatives.', 'start': 1621.767, 'duration': 5.865}, {'end': 1632.256, 'text': 'But if I ask you for the better solution, yes, what is the time complexity?', 'start': 1628.012, 'duration': 4.244}, {'end': 1640.608, 'text': "I can say I'm definitely iterating in the array and we're using a hash map to find and initialize in the hash map.", 'start': 1632.876, 'duration': 7.732}, {'end': 1646.437, 'text': 'So it can be logarithmic of a n if we are using ordered map in C++.', 'start': 1641.049, 'duration': 5.388}], 'summary': 'Discussed time complexity for a better solution using hash map. time complexity can be logarithmic of n if using an ordered map in c++.', 'duration': 30.874, 'max_score': 1615.563, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU1615563.jpg'}, {'end': 1712.791, 'src': 'embed', 'start': 1664.531, 'weight': 3, 'content': [{'end': 1670.097, 'text': 'Then this 1, that bico of 1 search time in the map ends up being bico of n.', 'start': 1664.531, 'duration': 5.566}, {'end': 1673.941, 'text': 'Hence the worst case can be n square if we use unordered map.', 'start': 1670.097, 'duration': 3.844}, {'end': 1677.104, 'text': 'So tell that to the interviewer that I can use unordered map.', 'start': 1673.961, 'duration': 3.143}, {'end': 1681.908, 'text': "If I do not have collisions, I'll end up having n cross 1, which is bico of n.", 'start': 1677.744, 'duration': 4.164}, {'end': 1685.572, 'text': 'and I will have n logarithmic of n.', 'start': 1682.609, 'duration': 2.963}, {'end': 1689.176, 'text': "If I'm using an ordered map, it will not have any collisions.", 'start': 1685.572, 'duration': 3.604}, {'end': 1696.843, 'text': "What will be the space complexity? The space complexity will be we're using a hash map where we are storing every prefix.", 'start': 1689.796, 'duration': 7.047}, {'end': 1702.287, 'text': 'So the worst case every index will have an individual prefix sum.', 'start': 1697.203, 'duration': 5.084}, {'end': 1706.709, 'text': 'So thereby a big O of n because all the prefix sum are stored.', 'start': 1702.767, 'duration': 3.942}, {'end': 1712.791, 'text': 'So this will be the time complexity and the space complexity for the better solution and for the optimal,', 'start': 1707.029, 'duration': 5.762}], 'summary': 'Using unordered map can lead to a worst case of n^2, while ordered map will have a space complexity of o(n).', 'duration': 48.26, 'max_score': 1664.531, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU1664531.jpg'}], 'start': 1506.501, 'title': 'Array and hash map optimization', 'summary': 'Covers optimizing code for arrays to handle negatives, zeros, and positives, leading to improved solutions and time complexity, as well as discussing the time and space complexity of iterating through an array using a hash map.', 'chapters': [{'end': 1632.256, 'start': 1506.501, 'title': 'Problem-solving with array optimization', 'summary': 'Discusses optimizing a code to handle edge cases with negatives, zeros, and positives in the array, leading to a better solution and time complexity analysis.', 'duration': 125.755, 'highlights': ['The code is partially accepted due to being the better solution for handling positives and zeros in the array, but further optimization is needed.', 'The optimized code runs for a problem with positives and negatives and is completely accepted.', 'Discussion on time complexity and identifying the optimal solution for handling positives and negatives in the array.']}, {'end': 1712.791, 'start': 1632.876, 'title': 'Hash map complexity analysis', 'summary': 'Discusses the time complexity of iterating through an array using a hash map, with a worst-case scenario of o(n^2) for unordered map and o(nlogn) for ordered map, and a space complexity of o(n) for storing every prefix in the hash map.', 'duration': 79.915, 'highlights': ['The worst-case time complexity can be O(n^2) for unordered map due to collisions, while it can be O(nlogn) for ordered map without collisions.', 'The space complexity is O(n) as every index may have an individual prefix sum stored in the hash map.']}], 'duration': 206.29, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU1506501.jpg', 'highlights': ['The optimized code runs for a problem with positives and negatives and is completely accepted.', 'The code is partially accepted due to being the better solution for handling positives and zeros in the array, but further optimization is needed.', 'Discussion on time complexity and identifying the optimal solution for handling positives and negatives in the array.', 'The space complexity is O(n) as every index may have an individual prefix sum stored in the hash map.', 'The worst-case time complexity can be O(n^2) for unordered map due to collisions, while it can be O(nlogn) for ordered map without collisions.']}, {'end': 2492.398, 'segs': [{'end': 1754.04, 'src': 'embed', 'start': 1712.791, 'weight': 0, 'content': [{'end': 1715.332, 'text': 'in case the array has positives and negatives.', 'start': 1712.791, 'duration': 2.541}, {'end': 1717.793, 'text': "Whenever you're telling the solution in an interview,", 'start': 1715.533, 'duration': 2.26}, {'end': 1724.696, 'text': 'make sure that you tell them about the better solution and then explain the edge case about zero and the negatives,', 'start': 1717.793, 'duration': 6.903}, {'end': 1728.638, 'text': 'and then tell them descriptively that that will only work for like.', 'start': 1724.696, 'duration': 3.942}, {'end': 1730.919, 'text': 'that will be the optimal solution for positives and negatives.', 'start': 1728.638, 'duration': 2.281}, {'end': 1739.966, 'text': 'But if the array just contains positives and zeros, I will turn to the most optimal solution that will be using the two pointer approach.', 'start': 1731.239, 'duration': 8.727}, {'end': 1742.828, 'text': "It'll be like a two pointer and a greedy approach.", 'start': 1740.386, 'duration': 2.442}, {'end': 1743.709, 'text': 'Very simple.', 'start': 1743.189, 'duration': 0.52}, {'end': 1745.331, 'text': "Let's start off.", 'start': 1744.25, 'duration': 1.081}, {'end': 1747.693, 'text': 'So the thought process is something like this.', 'start': 1745.771, 'duration': 1.922}, {'end': 1750.756, 'text': 'Before moving on to the dry run, let me tell you the thought process.', 'start': 1748.074, 'duration': 2.682}, {'end': 1752.018, 'text': "It's something like this.", 'start': 1751.217, 'duration': 0.801}, {'end': 1754.04, 'text': 'We have a single point.', 'start': 1752.578, 'duration': 1.462}], 'summary': 'In interviews, explain optimal solutions for arrays with positives, negatives, and zeros, using two pointer and greedy approach for positives and zeros.', 'duration': 41.249, 'max_score': 1712.791, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU1712791.jpg'}, {'end': 2075.638, 'src': 'embed', 'start': 2046.906, 'weight': 3, 'content': [{'end': 2049.927, 'text': "Okay, so let's quickly go into the compiler and try to code this up.", 'start': 2046.906, 'duration': 3.021}, {'end': 2052.929, 'text': 'If you want to try this problem, the link will be in the description.', 'start': 2050.206, 'duration': 2.723}, {'end': 2057.389, 'text': 'So we were having a left pointer as 0 and a right pointer as 0.', 'start': 2053.429, 'duration': 3.96}, {'end': 2058.751, 'text': 'And we were having a long, long sum.', 'start': 2057.389, 'duration': 1.362}, {'end': 2061.752, 'text': "So initially, what's the subarray? It's the single element.", 'start': 2059.031, 'duration': 2.721}, {'end': 2064.632, 'text': 'So sum will be array of 0.', 'start': 2062.252, 'duration': 2.38}, {'end': 2069.355, 'text': 'Perfect And we do one thing long, rather not, rather max.', 'start': 2064.632, 'duration': 4.723}, {'end': 2073.317, 'text': 'int will do max length is equal to 0.', 'start': 2069.755, 'duration': 3.562}, {'end': 2075.638, 'text': 'And int n equal to 8, 8 of size.', 'start': 2073.317, 'duration': 2.321}], 'summary': 'Using left and right pointers, initial subarray is single element with sum as array of 0. setting max length to 0 and n to 8.', 'duration': 28.732, 'max_score': 2046.906, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU2046906.jpg'}, {'end': 2278.671, 'src': 'heatmap', 'start': 2250.618, 'weight': 0.724, 'content': [{'end': 2255.1, 'text': "It is, let's quickly submit this and see if all the test cases do pass or not.", 'start': 2250.618, 'duration': 4.482}, {'end': 2257.201, 'text': 'This time, not really.', 'start': 2255.64, 'duration': 1.561}, {'end': 2258.862, 'text': 'And it is giving us a correct answer.', 'start': 2257.341, 'duration': 1.521}, {'end': 2263.184, 'text': 'So what I can say is this is an optimal solution.', 'start': 2259.442, 'duration': 3.742}, {'end': 2270.687, 'text': 'If the array contains positive and zeros, but if negative, then this is the optimal one.', 'start': 2263.384, 'duration': 7.303}, {'end': 2272.328, 'text': 'You cannot optimize this.', 'start': 2271.067, 'duration': 1.261}, {'end': 2278.671, 'text': 'Okay So what is the time complexity? On the naked eye, it might look like two while loops.', 'start': 2272.788, 'duration': 5.883}], 'summary': 'Optimal solution for array with positive, zeros, and negative numbers. time complexity appears to be two while loops.', 'duration': 28.053, 'max_score': 2250.618, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU2250618.jpg'}, {'end': 2453.176, 'src': 'embed', 'start': 2427.982, 'weight': 4, 'content': [{'end': 2434.006, 'text': 'What about the space complexity? No extra space, so a big O of 1.', 'start': 2427.982, 'duration': 6.024}, {'end': 2435.807, 'text': "That's what the optimal solution will be.", 'start': 2434.006, 'duration': 1.801}, {'end': 2442.05, 'text': 'And if you tell this entirely to the interviewer, he will be super duper impressed.', 'start': 2436.307, 'duration': 5.743}, {'end': 2445.652, 'text': 'So coming back to the sheet, I can see that these couple of problems are done.', 'start': 2442.391, 'duration': 3.261}, {'end': 2449.094, 'text': "With this, I'll be completing the step 3.1.", 'start': 2446.033, 'duration': 3.061}, {'end': 2450.695, 'text': 'And you can try this problem.', 'start': 2449.094, 'duration': 1.601}, {'end': 2452.096, 'text': 'Number of subarrays.', 'start': 2451.115, 'duration': 0.981}, {'end': 2453.176, 'text': 'This was the longest.', 'start': 2452.316, 'duration': 0.86}], 'summary': 'Optimal solution with o(1) space complexity will impress the interviewer. step 3.1 completed, try the problem of finding the number of subarrays.', 'duration': 25.194, 'max_score': 2427.982, 'thumbnail': ''}], 'start': 1712.791, 'title': 'Array summation and maximum length subarray', 'summary': 'Discusses optimal solution for finding array sum, addressing cases with positives, negatives, and zeros, introducing two-pointer and greedy approach. it also covers finding maximum length subarray with given sum using two-pointer approach, detailed breakdown of time and space complexity, with time complexity analyzed to be o(2n), and outlines steps to approach the problem.', 'chapters': [{'end': 1795.929, 'start': 1712.791, 'title': 'Optimal solution for array summation', 'summary': 'Discusses the optimal solution for finding the sum of array elements, addressing cases with positives, negatives, and zeros, and introducing the two-pointer and greedy approach.', 'duration': 83.138, 'highlights': ['The optimal solution for array summation is discussed, addressing cases with positives, negatives, and zeros.', 'The two-pointer and greedy approach is introduced as the most optimal solution for arrays consisting of positives and zeros.', 'The thought process for the two-pointer approach is explained, emphasizing the strategy of increasing summation and trimming from the left to maintain the desired sum.']}, {'end': 2492.398, 'start': 1796.87, 'title': 'Maximum length subarray', 'summary': "Introduces the concept of finding the maximum length subarray with a given sum using two-pointer approach and provides a detailed breakdown of the solution's time and space complexity, with the solution's time complexity analyzed to be o(2n). the chapter also outlines the steps to approach the problem and suggests a related problem for further practice.", 'duration': 695.528, 'highlights': ['The chapter introduces the concept of finding the maximum length subarray with a given sum using two-pointer approach', "Provides a detailed breakdown of the solution's time and space complexity", 'Outlines the steps to approach the problem and suggests a related problem for further practice']}], 'duration': 779.607, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/frf7qxiN2qU/pics/frf7qxiN2qU1712791.jpg', 'highlights': ['The optimal solution for array summation is discussed, addressing cases with positives, negatives, and zeros.', 'The two-pointer and greedy approach is introduced as the most optimal solution for arrays consisting of positives and zeros.', 'The thought process for the two-pointer approach is explained, emphasizing the strategy of increasing summation and trimming from the left to maintain the desired sum.', 'The chapter introduces the concept of finding the maximum length subarray with a given sum using two-pointer approach', "Provides a detailed breakdown of the solution's time and space complexity", 'Outlines the steps to approach the problem and suggests a related problem for further practice']}], 'highlights': ['The strybers a2z dsa course offers 456 modules.', 'Over 400 plus problems will be solved by the end of the course.', 'Completing this course provides the guarantee to clear DS algorithms of any company globally.', 'Using hashing to optimize subarray summation reduces time complexity from O(n^2) to a more efficient solution.', 'The brute force approach involves iterating through all possible subarrays using three nested loops, leading to a time complexity of approximately O(N^3)', 'The chapter emphasizes the importance of utilizing a map to store the prefix sum for efficient computation and retrieval of the required subarray length.', 'The process involves iterating through the array and maintaining a running sum, checking for subarrays with a specific sum.', 'The two-pointer and greedy approach is introduced as the most optimal solution for arrays consisting of positives and zeros.', 'The video covers finding the longest subarray with a given sum, discussing brute force and optimized solutions, and addressing array summation, maximum length subarray, and hash map optimization.', 'The chapter introduces the concept of finding the maximum length subarray with a given sum using two-pointer approach']}