Number of Submatrices That Sum to Target | Subarray Sum Equals K | Leetcode 1074 | Leetcode 560
Vložit
- čas přidán 9. 07. 2024
- Whatsapp Community Link : www.whatsapp.com/channel/0029...
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 - github.com/MAZHARMIK/Intervie...
Leetcode -1074 - github.com/MAZHARMIK/Intervie...
Leetcode-560 Link : leetcode.com/problems/subarra...
Leetcode-1074 Link : leetcode.com/problems/number-...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / 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
Apologies for the delay guys. I am packing for my next trip to Mussoorie.
I hope you guys will like the explanation.
Thank you all . Love you all ❤
Because of the trip, Contest problems will be delayed this week 🙏
Safe trip mik. Enjoy
Welcome to the UK, must visit Landour, Company Garden, George Everest & Mall road
Happy Musoorie trip
Have a safe & wonderful trip mik. ❣
Bhaiya itna mat ghumo, fomo hojata hai
It feels illegal to get this Dope content free of cost . Single handedly this guy is beating paid courses like scaler, gfg, bosscoder etc.
Hats off legend.
Enjoy the trip.
and striver too
CZcams pays him dont worry
There are so many youtubers who are very famous for teaching DSA but your channel is super underrated. I wish I had started my preparation by learning from your videos. Great work!!! Love your consistency and hard work
Before watching MIK's video this question was very verty HARD.
But after watching the dry-run it became too EASY.
Thanks a lot MIK .
Means a lot brother ❤️❤️🙏🙏
@@codestorywithMIK Bhaiya pls aage bhi content ko free hi rakhna pls, aaplke wajah se hi mein pechle 1 saal se LC mein consistent hoon(solved 534 ques till now).
No matter how tough the questions in the daily challenge may be, I find confidence knowing that if I stumble, you're there to turn the challenge into a piece of cake. Grateful for your support!
Thank You for this beautiful story.❣
If you get time then please tell us a story of today's weekly contest problem - 2,3,4... ❣
I was not able to solve question-2 :(
God level ❤
🙏🙏🙏❤️❤️❤️
u r the legend u r the best god bless u big brother love you , whenever i watch ur content u made my day
ek bar m hi chal gya code wo bhi without any error ... kya gazab ka smjahaya boss ek Number..
❤️🙏
I pray everyday to God for u...
U r such a gem Bhaiya❤❤
Means a lot brother 🙏🙏❤️❤️
This channel is a treasure
Thank you 👍
never heard of `1 Q's ke saath 1 free!`
thank, you're great work
Legit explanation. Hats off
Was waiting for your video since moring 😁 thanks a lot bhaiya ❤❤ and wishing you a great trip to Mussoorie 🙌
when you approach a problem it really seems like story telling
22:00, i dint knew how to find all submatrix till now, surprising i did not knew it
mujhe bhi aaj hi pta chla bhai 😅🫂
Amazing Explanation!! 🔥🔥🔥
WOW!!! best explaination possible
such a great explanation ... Loved it , i have personally seen all the available explanation present for this question ,but no one has explained it so perfectly
I am grateful that I found your Channel💫.
Clear explanation!
Once again god level explanation! 🔥🔥
That's some next level of explanation bro.
thanks for this wonderful explanation and the best part of this video is the dry run and thanks for that too keep rocking.
Thank you for your efforts :)
If you hadn't made this video then I wouldn't have understood this question in a milliion years!
❤️❤️🙏🙏
Happy trip mik.
Thank you for posting videos for us even during your trip ❤️❤️
waiting from morning nd wait is over now ❤
Hats off legend.
Can you please make the video on today's GFG POTD "Geekina Hate 1's" ?
I was able to tackle the problem with Brute Force but it required the more efficient approach. I think the optimized solution involves the Binary Search Algorithms which can reduce the range of numbers but I'm not able to code the actual logic for problem...
@codestorywithMIK please make the vdo
whenever i was not able to solve the leetcode POTD then i always wait for your video. your are just op OP EXPLANATION ❤💝
Thanks 👍
Best CZcamsr ever
masterpiece explanation
Got it brother. Awesome.
sir you are amazign with your effort,hardwork, and in-depth explaination wish you luck in your field
Your videos make me to do problems even if i know i stuck ti solve inner just try if not make it then mik is there ❤
Great video 👌
Have a safe & wonderful trip .
Thanks sir.
Thank you so much. You made it very clear and easy! Lots of love toward your concept, patience and explanation!!!
Glad it was helpful! 🙏❤️😇
Yo mik bhaiya, would u be covering today's B and D from the weekly?
I am travelling. But let me try asap ❤️🙏
@@codestorywithMIK Ok, safe travels❤❤
Thankyou sir
🤩 clear
You explained it very well sir but you missed the 2D sum approach method which is famous for this question
Before video problem very hard 😞
After watching video very easy🎉😂❤
387 weekly contests on leetcode question no. 2 solved due to this, question 😊
❤️❤️❤️
GOAT ✨✨
Hello Bhaiya, I urge you to make a video on today's gfg POTD , you are the only one who can explain that problem so that I can code it at my own.I have spend more than an hour on that problem but I can't get it
Yesterday's and today's questions were just 🤒
We're now 17k family.
Bhadayi hi MIK bhaijaan🎉😊
Bhai LC 2074 ek baar try kardo Bhai.
Bhaiya for the first problem , instead of inserting {0,1} in map for the first time, cant we check this with this code like : if(sum==0 ) count++; if(arr[i]==0) count++; ? Map me pehle insert karna intuition thoda hard laga, but it was worth it !!. Thanks for the content bhaiya ❤
Definitely you can do that too
Brother when you get time pls cover digit dp questions
🔥🔥
can u give us an insight on where to use a prefx sum type concept
Sir also make a solution video on today's leetcode weekely 382 contest of Q4 that is last Hard question using memoization becasue of that my today's day goes worse 😢. Also I am attatching my last Q4 answer below getting wrong answer in 551 testcase with memoization and got TLE in 613 testcase without memoization👇
class Solution {
private int solve(List list,int idx,int k,int[][] dp){
if(k==0 || idx==list.size()-1){
int min=Integer.MAX_VALUE;
int ans=0;
for(int i:list){
ans|=i;
}
min=Math.min(min,ans);
return min;
}
if(dp[idx][k]!=-1){
return dp[idx][k];
}
int n1=list.get(idx);
int n2=list.get(idx+1);
list.remove(idx);
list.remove(idx);
list.add(idx,n1&n2);
int take=solve(list,idx,k-1,dp);
list.remove(idx);
list.add(idx,n2);
list.add(idx,n1);
int skip=solve(list,idx+1,k,dp);
return dp[idx][k]=Math.min(take,skip);
}
public int minOrAfterOperations(int[] nums, int k) {
int[][] dp=new int[nums.length+1][k+1];
for(int i=0;i
Bhaiya,whenever possible please make a video on today's leetcode challenge. Unn questions ke solutions yt pe kaheen nahi hain
sir please explain gfg hard level potd questions also
Bhaiya please make videos on contest problems also
❤❤❤
Suggestion, change the channel name to something fancy will help you to grow (Insiders update)
19:21 main thing
Bro with your permission shall I post this video's link in my solution??
Yes please ❤️❤️🙏🙏
I always share his videos almost everywhere 😅
@@codestorywithMIK bro pls share your LC profile so that I can put that in the credit. 🙏
Thank You for this amazing video bhaiya...
but i have one doubt:
in code of second question we don't have any loop for startRow so we will get only those submatrix which contains first row always. so we won't get answer for the other submatrix which doesn't contains first row....
but your code is accepted.......How?
please clear my doubt bhaiya or anyone, it will be very helpful.
sir high quality per video record kijiya
can someone share the 2D array kadane problem number?
github.com/MAZHARMIK/Interview_DS_Algo/blob/master/DP/Maximum%20Sum%20Rectangular%20Submatrix%20in%20Matrix%20dynamic%20programming(2-D%20kadane).cpp
Bhaiya plz do Q4 of today's contest
Bhaiya please make a solution of leetcode weekly contest 382 last question solution 3022 question number
bhaiya is how to learn development in interview persecptive bhaiya
bhai aajke leetcode contest ki video aayengi kya??
bhaiya sliding window wali playlist banana ek.
czcams.com/play/PLpIkg8OmuX-J2Ivo9YdY7bRDstPPTVGvN.html&si=U4TluXjpHMNmeSKS
Will upload more on this soon.
Sir gfg ka potd kra do please
First viewer
Thank you Kundan ❤
Hail Mary brother
Mik bhaiyaa gfg potd 😢
I joined ur watsapp
@codestorywithMIK bhai ek doubt hai bipartite graph ke question mein leetcode 785, 886 dono question mein jab hum adj list banale hai from 2d matrix toh ek question toh uske 2 ways hai both have same logic but kiss
LEETCODE 886- THIS WAY OF ADJACENCY LIST WORKS
ArrayList gra=new ArrayList();
for(int i=0;i
The way of explaining is just 🔥 🫡