Range Sum of Sorted Subarray Sums | Learning Something New | Leetcode 1508 | codestorywithMIK
441Whatsapp Community Link : https://www.whatsapp.com/channel/0029...
This is the 19th Video of our Playlist "Heap : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a good Heap problem : Range Sum of Sorted Subarray Sums | Learning Something New | Leetcode 1508 | codestorywithMIK
In this video, we will learn something very important - "How to find all subarray sums of an Array in increasing/decreasing order using heap."
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Range Sum of Sorted Subarray Sums | Learning Something New | Leetcode 1508 | codestorywithMIK
Company Tags : will update soon
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Intervie...
Leetcode Link : https://leetcode.com/problems/range-s...
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | ...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will...
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And...
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Approach 1: Brute Force
In this approach, we generate all possible subarray sums and store them in a list, temp. Then, we sort temp and sum up the elements between the given indices left and right.
Time Complexity (T.C): O(n2logn)
Generating all subarray sums takes O(n2) since there are n(n+1)/2 possible subarrays.
Sorting the list of subarray sums takes O(n2logn).
Space Complexity (S.C): O(n2)
Storing all subarray sums requires O(n2) space.
Approach 2: Using a Heap
In this approach, we use a priority queue (min-heap) to keep track of the smallest subarray sums. We initialize the heap with the first element of each subarray starting at each index. We then repeatedly extract the smallest element from the heap, and if it is within the range, add it to the result. If the subarray can be extended, we push the next subarray sum back into the heap.
Time Complexity (T.C): O(n2logn)
Inserting and extracting elements from the heap takes O(logn), and we perform these operations for each subarray sum, resulting in O(n2logn).
Space Complexity (S.C): O(n)
The heap hols at most n elements at any time.
✨ Timelines✨
00:00 - Introduction
00:51 - Problem Explanation
04:01 - Brute Force
08:05 - Coding Brute Force
10:03 - Learn Something New
27:54 - Coding Approach-2
32:08 - Time and Space Complexity
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024