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

[@pastori2672]

easiest entry position question in 2024

[@adityansah]

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

[@ismailkarroud3129]

🤣🤣🤣🤣🤣🤣🤣

[@NeetCodeIO]

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

[@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!

[@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

[@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

[@sionkim5504]

What did I just watched

[@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

[@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 🎉

[@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

[@Marcox385]

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

[@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)

[@yang5843]

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

[@foreverbowie2720]

Another challenge for my memory again!!!

[@tasneemayham974]

Amazinggg NeetCode!! Amazing trulyy!!

[@mnaresh3382]

Just 5 min in the video, already getting goosebumps, you never fail to impress me, 👍

[@venkateshv626]

The first 17 mins is just the rudimentary brute force solution explanation. It’s after that will you feel the pain in ass.

[@mnaresh3382]

@@venkateshv626 just when I thought its easier than expected, had a whole new twist waiting patiently.

[@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.

[@jiteshpahwa266]

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

[@jfelipeff]

First hehe

[@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 😅

[@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.

[@kenamia9136]

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

[@StellasAdi18]

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

[@singletmat5172]

truly in the 7th layer of hell lol

[@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.

[@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.

[@varunpalsingh3822]

this was hard one !!

[@rostislav_engineer]

thank you

[@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?

[@MP-ny3ep]

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

[@rahulsiddhardh3701]

Best explanation on the internet today

[@nechiii-2863]

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

[@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 😅

[@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

[@rajsuriyang3427]

I don't have 500IQ😂.

[@BlunderArmour]

Neato! Great explanation as always.

[@krishnakanth4638]

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

[@LuisEDITS_KLK]

prob not but we came here for the explanation

[@diegobarbieri7804]

thats so fireee

[@sankalpchordia5245]

Best solution

[@jayrathod9271]

Second

[@BROOKnim]

lessgo

[@SalmanZaman]

Thanks.

[@talhajaved5417]

dankeschön

[@prasadm3614]

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

[@prasadm3614]

I love you NC