Number of Submatrices that Sum to Target - Leetcode 1074 - Python

[@NeetCodeIO]

Here's the video for LeetCode 560 that I mentioned: kzbin.info/www/bejne/nHe5i6dja9iar9E

[@adityansah]

What a lovely question for round 0 at a big tech company for Associate SDE Intern position.

[@ismailkarroud3129]

🤣🤣🤣🤣🤣🤣🤣

[@I.II..III...IIIII.....]

By far the best leetcode content on youtube. What I really appreciate is that compared to others you don't pretend these solutions are easy to come up with, even for medium problems. And that's exactly how you are able to explain them so well. Thank you for the great lessons you've taught me.

[@rafael84]

Wow, I was struggling to actually understand the formulas behind the 2D prefixSum, now I completely get it! The last part of the solution was indeed hard to grasp as well, but you once again gave us the best explanation ever! Thank you, Navdeep!

[@EduarteBDO]

I made the code a little short by increasing the sub_sum size by 1 with zeros so I don't get index out of bound and don't need the ifs. With that the first code passed with 9899ms. But I couldn't come up with a solution by myself. class Solution: def numSubmatrixSumTarget(self, matrix: list[list[int]], target: int) -> int: ROWS, COLS = len(matrix), len(matrix[0]) sub_sum = [[0] * (COLS+1) for _ in range(ROWS+1)] res = 0 for r in range(1, ROWS+1): for c in range(1, COLS+1): sub_sum[r][c] = matrix[r-1][c-1] + sub_sum[r-1][c] + sub_sum[r][c-1] - sub_sum[r-1][c-1] for r1 in range(ROWS): for r2 in range(r1, ROWS): count = defaultdict(int) # sub_sum -> count count[0] = 1 for c in range(COLS): cur_sum = sub_sum[r2+1][c+1] - sub_sum[r1][c+1] diff = cur_sum - target res += count[diff] count[cur_sum] += 1 return res

[@yooos3]

This is one of the problems that make you feel like "you're almost there" but not exactly. Solving 506 first made this a lot easier to understand (thanks for the recommendation and video). I have a love-hate relationship with these kinda problems.

[@binh-nguyen-d]

Best explanation! finally i cracked this challenging problem 🎉

[@kapilkhandelwal48]

In cpp it got accepted by the previous method also

[@natashasrivastava7024]

Thats what I was thinking.. I did previous method in java.. and accepted.. something with python I believe

[@abhaykumarsingh3884]

would you like share the solution??

[@rileysikes9285]

Truly the seventh layer of hell. Great explanation!

[@rahulsiddhardh3701]

Best explanation on the internet today

[@pastori2672]

easiest entry position question in 2024

[@MP-ny3ep]

This was a tough one , thank you for explaining it so well

[@estifanosbireda1892]

The hint from LeetCode was really useful in this question, that helped me get to the solution. But still implementation was also not direct, had to work with index carefully.

[@akhma102]

Thank you, Neet!

[@moviesins9226]

How in the world did you come with a solution for this? You are amazing. Salute!!

[@NeetCodeIO]

I'ma keep it real with you, I wasn't able to come up with the last optimization until I saw a post that said it's similar to Leetcode 560

[@XEQUTE]

keepin it real ! @@NeetCodeIO

[@kgCode658]

But the way you explain is amazing. Your video is as optimised as your solution. No redundancy 😅

[@imatleast12]

Recently I had to calculate the ∫ image to find haar like features, this is basically that. In numPy you can calculate the ∫ image by using a cumsum for the cols then the rows in just one line of code. Then to find the num of any rectangle you only need to add/subtract 4 values.

[@tasneemayham974]

Amazinggg NeetCode!! Amazing trulyy!!

[@kenamia9136]

understanding leetcode 304 "Range Sum Query 2D" will make this problem easier to deal with.

[@rostislav_engineer]

thank you

[@foreverbowie2720]

Another challenge for my memory again!!!

[@prasadm3614]

I am going to follow oncd my schedule is completed! I follow all your problems

[@prasadm3614]

I love you NC

[@BROOKnim]

i knew we are gonna use prefix sum. but could never come up with the fourloop to threeloop optimization , even after seeing the 1d array + map version. converting it to the 2d version wasnt intuitive to me. mayb im dumb :(

[@codenrun6013]

Same

[@1vader]

Leetcode actually accepted my version of solution 1, although just barely, 9.7s time, I assume the timeout limit is 10s. Faster than 5% of Python solutions 😅

[@piyushgupta7210]

my brain hurts now.. i was able to come up with the first solution and got TLE for 3 testcases. 37/40 passed.. however i don't think i would have thought of 2nd solution ever...

[@Alexander-zt9kz]

Nobody would have been able to, the best solution I was about to come up by myself with prefix sums was O(n^3), so a bit better than O(n^4)

[@BlunderArmour]

Neato! Great explanation as always.

[@yaswanthkosuru]

i used to spent 2 hours to solve problem am i wasting time the key is if we have prefix sum how to get number of sub array with given target

[@PrakashLight-vs1nj]

Same here

[@varunpalsingh3822]

this was hard one !!

[@sankalpchordia5245]

Best solution

[@SalmanZaman]

Thanks.

[@StellasAdi18]

Correct me should formula be Matrix[r2][c2]+ subsum[r1-1][c2]+ subsum[r2][c1-1] - subsum[r1-1]c1-1]?

[@ayanpatel_98]

why do you need to new create count default dict again for every r1 and r2? why not use the same count dictionary?

[@talhajaved5417]

dankeschön

[@diegobarbieri7804]

thats so fireee

[@superironbob]

What circle of hell is it that I actually got this problem in an interview?

[@narendramauryaa]

For what position?

[@kgCode658]

Fkkk

[@kgCode658]

Even after solving 1k problem I don't think anyone can come up with this soln

[@CS_n00b]

What company?

[@superironbob]

It was for a senior dev position at Google, but it was also the day they announced their first layoffs. I don't know if that's related but I'd suspect it was.

[@yuvarajuv1006]

How iterating through 4 loops gives us all submatrices , I am not able to get the intution . sry if i am dumb, these 2d matrix problems give me headaches

[@jfelipeff]

First hehe

[@ferdinanddebaecque2723]

Thanks for the explanation ! but I don't understand why we initialize `count[0] = 1` in the last part, what does it mean ? does someone have a simple explanation please ?

[@codenrun6013]

Basically empty sub matrix is also considered, sum of that part is 0. That why we store the count as 1, which means that we have a chunk that sums upto to zero, i.e when we remove nothing from our running sum can we acheive target, if yes then ans += 1 for that case as well

[@yang5843]

Another question to make you walk out of the interview if you get asked it.

[@krishnakanth4638]

Have u come up the solution of this problem by ur own

[@LuisEDITS_KLK]

prob not but we came here for the explanation

[@singletmat5172]

truly in the 7th layer of hell lol

[@sionkim5504]

What did I just watched

[@Marcox385]

Another day, another brain cell Lose a few every time a hard problem comes up

[@jayrathod9271]

Second

[@BROOKnim]

lessgo

[@jiteshpahwa266]

What was this question mannn !!!!!!!!

[@rajsuriyang3427]

I don't have 500IQ😂.

[@nechiii-2863]

i'll be honest ! it will take me ages to become this dude......