Spiral Matrix - Microsoft Interview Question - Leetcode 54

0:00 - Read the problem
1:10 - Drawing explanation
9:50 - Coding explanation

leetcode 54

#microsoft #matrix #python

[chegehimself]

for line 16 we can replace it by checking the size of _res_ . _size = m x n_

_if not (left < right and top < bottom):_
_break_
to
_if len(res) == size:_
_break_

[PallNPrash]

Great, clear explanation, as ALWAYS!! Thank you SO much!! Lots of gratitude and respect...Hope you know how much this helps those trying to prepare for programming interviews.

[shivanshsingh]

I was having a hard time understanding from the discussion section, but understood it immediately by watching your video.

[almaspernshev]

Great explanation as always, but I would like to add if someone gets confused by the termination condition:

Use DeMorgan's Law: not (A and B) == not A or not B == left >= right or top >= bottom

[aaroncassar]

I had this question on a job interview last week. This was how I was going to solve the problem but they told me I should find an easier solution instead. They had me rotate and rebuild the matrix, removing the top row each time.
While that was significantly easier and cleaner than this solution, they didn't seem to recognize / care about the inefficient time and space complexity of that solution when I informed them :/

[Oda]

Cannot imagine doing leetcode without NeetCode

[sooryaprakash]

Happy Teacher's day man ! Specifically chose a old video to comment because they were helpful to me .

Thank you for your contribution.

[wlcheng]

Using reversed for the bottom and left rows would be easier to understand the code. :)
for i in reversed(range(left, right)):
res.append(matrix[bottom - 1][i])
bottom -= 1

for i in reversed(range(top, bottom)):
res.append(matrix[i][left])
left += 1

[michadobrzanski]

Good one, however you oversimplify this break statement. It is a very crucial code element that makes the algorithm correct and it should be explained in detail.

How you can explain it:
- tell that before introducing those breaks the while loop has && statement and no breaks, so we can end up in either left < right not met or top < bottom not met (for a last iteration):
- explain that only after the END of the loop the condition is checked
- insert early breaks in strategic places:
1. insert if(top == bottom) break after first for-loop -> as we increment top, so we might end up in equal with bottom
2. insert if (left == right) break after second for-loop -> as we decrement right, so we might end up in equal with left

This is to prevent going again into the same fields.

[romo]

Solution with recursive dfs made more sense to me. Just use a queue of directions and pop and re-add when you can't go in that direction anymore

[camoenv]

Here's a (very) slightly less efficient solution that's easier to code. It will do two additional loops in some cases, since we don't have the 'break' condition after going [left to right] and [top to bottom]. Instead, we break the while loop only when our results array is >= the total number of elements in the matrix. Then, we return only the first N elements (throw away the extra work that may have been done by the [right to left] and [bottom to top] loops). Overall time complexity and space complexity should be essentially the same.

def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix: return []
rows, cols = len(matrix), len(matrix[0])
tot = rows * cols
topR, botR, lCol, rCol = 0, rows-1, 0, cols-1

res = []
while len(res) < tot:
for i in range(lCol, rCol+1):
res.append(matrix[topR][i])
topR += 1

for i in range(topR, botR+1):
res.append(matrix[i][rCol])
rCol -= 1

for i in reversed(range(lCol, rCol+1)):
res.append(matrix[botR][i])
botR -= 1

for i in reversed(range(topR, botR+1)):
res.append(matrix[i][lCol])
lCol +=1

return res[:tot]

[NhanSleeptight]

Thank you so much for the explanation. I want to do leetcode every day with your videos

[Aryan]

*explanation for* : _if not (left < right and top < bottom): break_
since we updated top and right variable, we should check if while loop condition is still correct

Alternatively: this might be easier to follow
'''
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
l, r = 0, len(matrix[0])
t, b = 0, len(matrix)

res = []
while l < r and t < b:
# get every i in the top row
for i in range(l, r):
res.append(matrix[t][i])
t +=1

# get every i in the right col
for i in range(t, b):
res.append(matrix[i][r-1])
r -=1


*if (l<r and t<b):*

# get every i in the bottom row
for i in range(r-1, l-1, -1):
res.append(matrix[b-1][i])
b -=1

# get every i in the left col
for i in range(b-1, t-1, -1):
res.append(matrix[i][l])
l +=1

return res
'''

[PankajKumar-pvog]

I saw few videos on youtube but the way you explained with drawing explanation, it let us visualise the solution in our head, awesome man. thanks

[WholeNewLevel]

This solution in JS, for those of you who wondering


var spiralOrder = function(matrix) {
let res = [];
const rows = matrix.length;
const cols = matrix[0].length;
let left = 0, right = matrix[0].length-1;
let up = 0, down = matrix.length-1;

//[up, down][left, right]
while(left <= right && up <= down ){

for(let i=left;i<=right;i++){
res.push(matrix[up][i])
}
up+=1;
for(let i =up;i<=down;i++){
res.push(matrix[i][right])
}
right-=1;
if(left > right || up > down ) break;

for(let i = right;i >= left;i--){
res.push(matrix[down][i])
}
down-=1;
for(let i=down;i>=up;i-- ){
res.push(matrix[i][left])
}
left+=1;

}

return res

};

[rishikaverma]

absolutely love how you explain such complex problems with such clarity

[bankea.]

Thank you :) i am glad i really attempted to solve the question for 2 hours before looking at your solution. Once you started explaining it was easier for me to understand where the solution

[KateRipley]

this was a great explanation! I loved the drawings and the step by step walkthrough in the beginning. And you spoke so clearly too :)

[nguyenbach]

Jesus the way u make everything easier is so gud thanks a lot

[shenzheng]

Your answer is always clear and concise. The universities should hire more teachers like you, not PPT readers like my professors :).