Number of Submatrices That Sum to Target | Subarray Sum Equals K | Leetcode 1074 | Leetcode 560
384Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 80th Video of our Playlist "Array 1D/2D Programming : Popular Interview Problems".
In this video we will try to solve two very good Array problems -
Subarray Sum Equals K (Leetcode 560)
K Inverse Pairs ArrayNumber of Submatrices That Sum to Target (Leetcode 1074)
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 : K Inverse Pairs ArrayNumber of Submatrices That Sum to Target | Subarray Sum Equals K | Leetcode 1074 | Leetcode 560
Company Tags : Meta, Amazon, Netflix, Apple, Google, Amazon
My solutions on Github(C++ & JAVA) :
Leetcode - 560 - https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Arrays/Subarray%20Sum%20Equals%20K%20(O(n)).cpp
Leetcode -1074 - https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Arrays/2-D%20Array/Number%20of%20Submatrices%20That%20Sum%20to%20Target.cpp
Leetcode-560 Link : https://leetcode.com/problems/subarray-sum-equals-k/
Leetcode-1074 Link : https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Approach Summary (Leetcode-560) : The approach uses a map (mp) to keep track of cumulative sums encountered during the iteration through the input array. It initializes sum to zero and increments it as it iterates through the array. The map is used to store the count of each cumulative sum. The algorithm checks if the difference between the current cumulative sum (sum) and the target value (k) exists in the map. If it does, it adds the corresponding count to the result. Finally, the count of the current cumulative sum is updated in the map. The function returns the total count of subarrays with the sum equal to k.
Approach Summary (Leetcode-1074) : The approach involves iterating through all possible starting and ending points (rows and columns) of submatrices within the given matrix. For each combination of starting and ending points, it calculates the sum of elements within the submatrix and increments the result count if the sum matches the target. The function returns the total count of submatrices with the sum equal to the target. This solution has a time complexity of O(m^2 * n^2), where 'm' is the number of rows and 'n' is the number of columns in the matrix. It can be optimized further using precomputation or dynamic programming techniques.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
00:31 - Leetcode-560 Problem Explained
1:46 - Leetcode-560 Brute Force
4:25 - Leetcode-560 Optimal Intuition with Dry Run
16:53 - Leetcode-560 Live coding
19:12 - Leetcode-1074 Problem Explained
21:14 - Leetcode-1074 Brute Force
24:46 - Leetcode-1074 Optimal Intuition with Dry Run
51:25 - Leetcode-1074 Live coding
#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 #2024 #newyear