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

First hehe

lessgo

Second

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

Thanks.

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

Best explanation on the internet today

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 :(

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

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

What did I just watched

dankeschön

In cpp it got accepted by the previous method also

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

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

Correct me should formula be

Matrix[r2][c2]+ subsum[r1-1][c2]+ subsum[r2][c1-1] - subsum[r1-1]c1-1]?

Best solution

Best explanation! finally i cracked this challenging problem 🎉

this was hard one !!

easiest entry position question in 2024

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

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 ?

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

thats so fireee

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

I don't have 500IQ😂.

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.

Neato! Great explanation as always.

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.

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

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

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 😅

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!

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

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

Truly the seventh layer of hell. Great explanation!

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.

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

truly in the 7th layer of hell lol

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

Amazinggg NeetCode!! Amazing trulyy!!

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

Another challenge for my memory again!!!

thank you

Thank you, Neet!

starting 2025 with this... I promise to myself, I will crack FAANG this year.