Number of Submatrices that Sum to Target - Leetcode 1074

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

Рет қаралды 13,309

Күн бұрын

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/number-...
0:00 - Read the problem
1:03 - Explanation 1
12:23 - Solution 1
17:30 - Explanation 2
27:32 - Solution 2
leetcode 1074
#neetcode #leetcode #python

Пікірлер: 64

@adityansah 5 ай бұрын

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

@ismailkarroud3129 3 ай бұрын

🤣🤣🤣🤣🤣🤣🤣

@pastori2672 5 ай бұрын

easiest entry position question in 2024

@NeetCodeIO 5 ай бұрын

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

@MP-ny3ep 5 ай бұрын

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

@binh-nguyen-d 5 ай бұрын

Best explanation! finally i cracked this challenging problem 🎉

@kapilkhandelwal48 5 ай бұрын

In cpp it got accepted by the previous method also

@natashasrivastava7024 5 ай бұрын

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

@I.II..III...IIIII..... 3 ай бұрын

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.

@rahulsiddhardh3701 5 ай бұрын

Best explanation on the internet today

@rafael84 5 ай бұрын

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!

@tasneemayham974 5 ай бұрын

Amazinggg NeetCode!! Amazing trulyy!!

@SalmanZaman 5 ай бұрын

Thanks.

@mnaresh3382 5 ай бұрын

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

@venkateshv626 5 ай бұрын

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

@mnaresh3382 5 ай бұрын

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

@yooos3 5 ай бұрын

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.

@EduarteBDO 5 ай бұрын

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

@BlunderArmour 5 ай бұрын

Neato! Great explanation as always.

@estifanosbireda1892 5 ай бұрын

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.

@sankalpchordia5245 5 ай бұрын

Best solution

@varunpalsingh3822 5 ай бұрын

this was hard one !!

@foreverbowie2720 7 күн бұрын

Another challenge for my memory again!!!

@moviesins9226 5 ай бұрын

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

@NeetCodeIO 5 ай бұрын

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 5 ай бұрын

keepin it real ! @@NeetCodeIO

@kgCode658 5 ай бұрын

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

@imatleast12 5 ай бұрын

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.

@talhajaved5417 5 ай бұрын

dankeschön

@rileysikes9285 5 ай бұрын

Truly the seventh layer of hell. Great explanation!

@kenamia9136 5 ай бұрын

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

@1vader 5 ай бұрын

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 😅

@diegobarbieri7804 5 ай бұрын

thats so fireee

@ayanpatel_98 5 ай бұрын

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

@BROOKnim 5 ай бұрын

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 5 ай бұрын

Same

@yuvarajuv1006 5 ай бұрын

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

@StellasAdi18 5 ай бұрын

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

@yaswanthkosuru 5 ай бұрын

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 5 ай бұрын

Same here

@ferdinanddebaecque2723 5 ай бұрын

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 5 ай бұрын

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

@piyushgupta7210 5 ай бұрын

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 5 ай бұрын

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 5 ай бұрын

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

@jfelipeff 5 ай бұрын

First hehe

@superironbob 5 ай бұрын

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

@narendramauryaa 5 ай бұрын

For what position?

@kgCode658 5 ай бұрын

Fkkk

@kgCode658 5 ай бұрын

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

@CS_n00b 5 ай бұрын

What company?

@superironbob 5 ай бұрын

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.