Magic Squares In Grid - Leetcode 840 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
5:03 - Coding Explanation
11:44 - Drawing Explanation 2
19:51 - Coding Explanation 2

leetcode 840

#neetcode #leetcode #python

[yang]

You didn't think the Leetcode problems could get worse, yet here we are.

[gmh]

this week is just the worst problems week, there's no category, and leetcode knows it

[NishaRathod-eurw]

Didn't feel like doing this problem, but streak :(

[jeffhappens]

That second solution is awesome. Idk, I get excited seeing math solutions with these logic tricks. It's like finding a trap door. If this wasn't for leetcode, i'd be feeling more positively about this

[gowtham_codes]

Me to me after going through 15:52: that’s cool, let’s settle for the FIRST OPTIMAL SOLUTION.

[hithambasheir]

Got the intuition and did a slightly different solution, did a few optimizations (with less readability) in the isMagic method
def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
if len(grid) < 3 or len(grid[0]) < 3:
return 0

def isMagic(r, c):
cols = [0 for _ in range(3)]
rows = [0 for _ in range(3)]
diags = [0 for _ in range(2)]
seen = set()
for i in range(r, r+3):
for j in range(c, c+3):
if grid[i][j] in seen or not (1 <= grid[i][j] <= 9):
return 0
seen.add(grid[i][j])
if r - i == c - j:
diags[0] += grid[i][j]
if i + j == r + 3 - 1 + c:
diags[1] += grid[i][j]
cols[j % 3] += grid[i][j]
rows[i % 3] += grid[i][j]
diags.append(15) #So dumb of me so I don't have to do an extra check down there lol XD

for i in range(3):
if not (cols[i] == rows[i] == diags[i] == 15):
return 0
return 1

res = 0
for r in range(len(grid) - 2):
for c in range(len(grid[0]) - 2):
res += isMagic(r, c)
return res

[MP-nyep]

Thank you so much for the daily leetcode.

[rambabupatidar]

the way you explained second approach seems a piece of cake now. Thank you very much🙌

[gary]

Thanks for the explanation! But I don't think the question mentioned that the sum of each row/col/diag is 15.

[elliottkau]

In the second solution, won't it fail on a grid that follows the rotational pattern but puts the odds in the corners and evens in the edges? Should there also be a second condition on pattern checking that makes sure [r-1][c] is odd?

[gowtham_codes]

Raise your hands if your brain got rotated at 19:00 😂🙋‍♂️

[ky.castillo]

two 20+ min solution vids in one week. god help us

[Graveness]

simpler optimization is calc prefix sum of rows and cols then check sub matrix is 45 if yes run check for magic square

[tunno]

Got a similar brute force Approach but nice explaination!

[arnavchauhan]

implementing the brute force approach gives
0ms Beats 100.00% in java wow
😂😂

[galkk]

I liked the math solution, hard to think about it but it's pretty nice

[varunallagh]

can u tell whee is it written that sum should be 15

[FahmiJemal-tl]

we were challenged by this problem when we were a kid

[InquisitiveLittleSteps]

Is the possible equal sum always 15? How can we arrive at that conclusion? Please Help...

[roderickli]

why do the rows cols and diag sum up to 15?