Spiral Matrix - Microsoft Interview Question - Leetcode 54

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@mdmehedihasan96]

It's a good platform.. thanks to you.

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

[@anchitbhushan6172]

Nice Observation

[@ganjinaveen7338]

Superb logic

[@stevenayare6097]

I think he wanted to keep left and right border logic consistent

[@draugno7]

I did that when solving this in june

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

[@NeetCode]

Thank you for the kind words, it means a lot!

[@almaspernshev7370]

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

[@rojo_pes75]

Thanks 🎉❤

[@shivanshsingh176]

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

[@aaroncassar7639]

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

[@expansivegymnast1020]

Huh never thought about doing that

[@prepat2133]

wow it was probably your interviewer who was just being dumb

[@namoan1216]

I have no ideas. Can you explain more/

[@paragggoyal1552]

who were they and how stupid can they be? that they can't recognize the inefficiency, not caring is one thing and not recognizing is completely different thing.

[@Oda3908]

Cannot imagine doing leetcode without NeetCode

[@sooryaprakash6390]

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

[@milesba4]

This is so much better

[@romo119]

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

[@osasikemwenogieva6998]

I used an array of directions and modulo four'd it

[@camoenv3272]

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

[@Aryan91191]

*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

[@wanderingcatto1]

What I don't understand is, the while loop says "while left < right and top < bottom". Hence, "if not left < right and top < bottom", this already violates the while loop condition. Shouldn't the while loop therefore break by itself, without having to write an explicit line of code to do this?

[@Fran-kc2gu]

the break looks more clean, this is ugly

[@PankajKumar-pv7og]

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

[@michadobrzanski2194]

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.

[@abhimanyuambastha2595]

He missed explanation of the only real edge case that gets people. "Trust me bro", not very neetcode is it?

[@provarence7361]

@@abhimanyuambastha2595 lol fr, you're just gonna have to trust me bro

[@dheerajgowda9208]

Thanks @michadobrzanski2194, your comment was helpful

[@rishikaverma9846]

absolutely love how you explain such complex problems with such clarity

[@bankea.8153]

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

[@WholeNewLevel2018]

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 =up;i-- ){ res.push(matrix[i][left]) } left+=1; } return res };

[@halahmilksheikh]

Having the >= checks in the while loop makes it so much more readable. No need to deal with the +1 or -1s like in the video solution.

[@nguyenbach4710]

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

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

[@shenzheng2116]

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

[@Ben-pb7ct]

One of the best explanation. Thank you

[@ОлегЄлечко]

I was doing that in quite confusive and unclear way) more mathematical) but your way is much better)

[@CST1992]

13:00 You just wrote the opposite of the condition of the while loop here. So basically you are trying to terminate it in the middle without iterating right to left and bottom to top.

[@ryanben3988]

Was missing out line 17 and 18😂😂 test case [[1,2,3]] was literally killing me, I almost hard coded it

[@DavidDLee]

Don't you need to check the ending condition (L7 or L18-19) after every for loop? If not, why in two places, not just one? 12:57 "Trust me on that" is not convincing.

[@fullstack_journey]

yes, yes you would. or rather make this the while terminating condition itself and trim out any excess u get.

[@wanderingcatto1]

I really still don't understand the part about "if not (left < right and top < bottom): break". The while loop on the top already states "while left < right and top < bottom", so "if not left < right and top < bottom", this already violates the while loop condition. Shouldn't the loop should logically break by itself, without having to write additional line of codes explicitly to do it?

[@NobleSpartan]

After completing the top to bottom traversal, the break condition checks if there's still a "rectangle" to traverse. If there isn't, that means we reached the center col and we don't need to traverse anymore. You can replace the break by checking if the loops that traverse right-to-left and bottom-to-top still have rows/cols left before changing the pointers. (i.e) if top < bottom: for i in reversed(range(left,right)): res.append(matrix[bottom - 1][i]) bottom -= 1 if left < right: for i in reversed(range(top,bottom)): res.append(matrix[i][left]) left += 1

[@wayne4591]

I do it in basically the same manner, but I put the right and bottom pointer right at the last element of the rows and cols, the pro is that you don't have to worry about recount the corner element when you shift directions, but the con is that this way doesn't work with the last row or column. So, you will have to add two ifs in the last of your code to handle either situation where you have a single row or column left in the last. But overall, I found this more straightforward in logic and it saves a lot of time since you don't have to deal with corner indexing when you are coding.

[@evelyntromp789]

Your videos are absolutely amazing! Thank you so much!

[@bhardwajatul09]

Very well explained.... Your video made this complex problem very easy 👏👏👏👏

[@chandrakethans5835]

Thank you so much was scared of this question earlier not anymore

[@just_hexxy]

thank you very much for this video! it was great and simple code. I'd like to provide one suggestion tho: would be helpful if while you're writing the code, you referred back to the drawings as well, for people who find it harder to visualize (like myself).

[@abhilashsingh439]

Thank you so much..i was stuck in this problem for more than an hour

[@riddle-me-ruben]

With this, I was able to solve spiral matrix 1,2 and 4

[@nikhildinesan5259]

Was doing the same ques just yesterday😊..

[@sachinfulsunge9977]

You make it look so simple!

[@nehabhavsar4943]

Clear and simple explanation as always. Thank you so much!

[@CST1992]

I got a "96% faster" with this solution, thanks!

[@akhilchandra5935]

Thanks!

[@MinhNguyen-lz1pg]

Great video. Hmm, I see, if we don't check it half way, says we have single row, then we basically append the same row forward and backward to the result haha

[@Anirudh-cf3oc]

Great, clear explanation, as ALWAYS!! Thank you SO much!!

[@prateekgoyal3353]

class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: return matrix and [*matrix.pop(0)] + self.spiralOrder([*zip(*matrix)][::-1]) copied!

[@Moch117]

Thanks for showing the world your garbage code

[@loke_mc8053]

came here at 8/824 as a lc daily challenge was spiral 3,so came to 1 and going 2 from her till 3rd

[@salimzhulkhrni1610]

Clear and simple explanation. Keep up the great work as always sir! :)

[@chibitoodles5351]

path = [] while len(matrix)>1: rowfirst = matrix[0][:len(matrix[0])-1] rowlast = matrix[-1][:len(matrix[-1])-1] rowlast = rowlast[::-1] rowmid = [i[-1] for i in matrix] path = rowfirst+rowmid+rowlast matrix.remove(matrix[0]) for i in matrix: i.remove(i[-1]) matrix.remove(matrix[-1]) path.extend(matrix[0]) print(path) Does this work as an efficient solution?

[@EnterThumsUp]

You made this dead easy Thankyou so much 😘

[@MP-ny3ep]

Great explanation as always . Thank you.

[@saichandu8178]

We can use DFS with order Right, Down, Left, Up

[@sidazhong2019]

for i in range(right-1,left-1,-1): same as: for i in reversed(range(left,right)): easier to understand.

[@netraamrale8119]

this is best channel

[@mnchester]

amazing explanation!

[@abhinavs2484]

got this qsrtn asked at Microsoft recently, I gave a recursive solution

[@nikhilgoyal007]

note to self - corner cells did not get added twice since top pointer changed.

[@Roshan-xd5tl]

Great and amazing explanation as always. Thank you!! Cheers :)

[@maamounhajnajeeb209]

you made it easy, thanks man.

[@NeetCode]

Glad it helped!

[@sannge6471]

Very easy to understand!

[@Ben-pb7ct]

Could anyone explain a line of the code in the middle: if(left >= right || top >= bottom) ? I am writing this in C++ language so it is why it looks a little bit different from python. Also, I feel confused when I copy that line of code like if(left >= right && top >= bottom), my compiler tells me it's an error but if I re-write it as if(left >= right || top >= bottom), it's correct now. Why the video author doesn't get the error?

[@NeetCode]

i put a 'not' in front of it, i think "if not (left < right and top < bottom)" in c++ would be "if !(left < right && top < bottom)", so ! instead of not. But the way you wrote it is probably better and more readable.

[@Ben-pb7ct]

@@NeetCode thank you so much for the kind reply. I just subscribe you. Again, I appreciate it ! It really helps me a lot

[@roses7390]

This was super helpful. Thank you

[@prtk_m]

Thank you for the great vid! One thing, the Spiral Matrix solution done by Nick White in Java had a runtime of 1MS with the exact same algorithm -- Is this just because Java processes it quicker because of the JVM?

[@avenged7ex]

Yes, on the whole Java executes much faster than Python. In these cases, it's best to compare Leetcode's runtime distribution for the language you're using - as a language like C will execute this code much quicker than Python.

[@mohithadiyal6083]

Best explanation

[@ms3801]

Such a good explanation on this thank you

[@NaveensinglaYT]

i think there should be || instead of && at line 16 because at GFG it is not accepting if i put a && operator over there

[@amritpatel6331]

Awesome explantion.

[@amankassahunwassie587]

I think my code looks easier to understand, check it res =[] left, right = 0, len(matrix[0])-1 top, bottom = 0, len(matrix)-1 while left

[@jerrychan3055]

Here is a dfs solution class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: m, n = len(matrix), len(matrix[0]) visited = set() res = [] ds = [ [0, 1], # right [1, 0], # down [0, -1],# left [-1, 0] # up ] self.idx = 0 def dfs(r, c): if r < 0 or r == m or c < 0 or c == n or (r, c) in visited: self.idx += 1 return visited.add((r, c)) res.append(matrix[r][c]) for _ in range(4): i = self.idx % 4 dr, dc = ds[i][0], ds[i][1] dfs(r + dr, c + dc) dfs(0, 0) return res

[@factopedia1054]

A BIG Thanks ❤️

[@___vijay___]

great explanation!!

[@aumrudhlalkumartj6343]

Great explanation. Thanks

[@chujunlu919]

Thank you for the great explanation! Do you plan to work through another simulation question 498. Diagonal Traverse? I hope to see how you approach it.

[@OneAndOnlyMe]

A helper function would also increase memory use too, so in this case, it's more efficient to write the four loops, and it's easier to follow too.

[@srikanthvelpuri2973]

great work from you keep it up

[@aakashbhatia]

Good explanation

[@nikhilnagarapu3077]

Great Explanation!!

[@salimshamim3851]

I was redoing this question after a while, and I got almost everything right, but that middle line of code where we are checking if left < right and top < bottom. Has anyone have the intuition? what prompts you to put that there? Help

[@raunakthakur7004]

What would be the complexity here? I am guessing o(M) is time and o(m) is the space as well?

[@dayanandraut5660]

O(m*n) is time complexity and O(1) is the space complexity. No additional space has been used. The list to store the values doesn't count as additional space

[@tb8588]

@@dayanandraut5660 hmm why don't you count the list to store the values? it is still additional space being used no? Can you explain why the time complexity is O(m*n)

[@dayanandraut5660]

@@tb8588 we are traversing the matrix of m * n size. Each cell is traversed only once. That's why, time complexity is m*n. And yes if you considered space for storing the results, space complexity is m*n. Otherwise, its constant.

[@utkarshashinde9167]

Thanks a lotttt it helped

[@halahmilksheikh]

Why do we have the break in the middle of the code? If you put it somewhere else, it doesn't work. And why do we not have to check after each for loop?

[@redietyishak8278]

Thanks, that helped a lot!!!

[@expansivegymnast1020]

Good video!

[@UnemployMan396-xd7ov]

Banger

[@Techgether]

shouldnt line 23 be jus top instead of top -1? u dont want to include top -1 element since its has been added above

[@danielcarlossmd]

Thank you

[@tb8588]

Is the time complexity for this question O(min(m, n)*max(m, n)) ? and the space complexity O(m*n)

[@yang5843]

The time complexity is O(m*n) because every value is looked at

[@rohitkumarsinha876]

love your work bro'

[@ianbulack4539]

Would someone mind explaining why the if not (left < right and top < bottom): break statement is necessary? Because it's already in a while left < right and top < bottom loop. Does python not check that value during the first loop? I must be missing something here, would someone mind explaining? Thank you!

[@hongminwang2507]

Commenting out the line 16 and 17 results in this mistake: Input: [[1,2,3,4],[5,6,7,8],[9,10,11,12]] Output: [1,2,3,4,8,12,11,10,9,5,6,7,6] Expected: [1,2,3,4,8,12,11,10,9,5,6,7] The reason is that top and right are updated in the first two for loops, it can happen that only one of the two conditions (left < right and top < bottom) does not hold anymore and the process should terminated immediately. Otherwise, if it continues with the remaining two for loops, one of them does nothing because of the empty range(), fine, but the other for loop would still append extra elements to the res list before breaking out of the outer while loop and return.

[@spacetime_wanderer]

@@hongminwang2507Excellent response. In Neetcode’s terminology used here - after the first two loops (parse left to right and parse top to bottom) it may stop being a rectangle if left == right OR top == bottom. So further two iterations are not applicable for a non rectangle.

[@johnsoto7112]

H,i can anyone clarify the edge case on line 18. If there’s 1 array in the matrix, wouldn’t we go out of bounds at line 11 and get an error at line 14 when trying to loop from top to bottom?

[@freesoul2677]

Thank you!!

[@chegehimself]

Why is this not working for line 16? _if right < left and bottom < top:_ _break_

[@igoragoli]

I love you.

[@namdo0512]

i have this code on the internet but i can't get it, can so explain me plz: n = input('square') dx, dy = 1,0 x, y = 0,0 spiral_matrix = [[None] * n for j in range(n)] for i in range(n ** 2): spiral_matrix[x][y] = i nx, ny = x + dx, y + dy if 0

[@arjunprasad1071]

Thanks, that was a fantastic explanation💯💯 I was trying the problem for long, had reached the same approach as yours, but was making mistakes. That boundary making thing was the enlightment😁. C++ code for the same below ✔👇 : class Solution { public : vector spiralOrder(vector& matrix) { vectorans; int left_boundary = 0; int right_boundary = matrix[0].size(); int top_boundary = 0; int bottom_boundary = matrix.size(); int ele; while(left_boundary < right_boundary and top_boundary < bottom_boundary) { //left to right int j=left_boundary; while(j=top_boundary) { ele = matrix[j][left_boundary]; ans.push_back(ele); j--; } left_boundary++; } return ans; } };

[@VaraPrasad0004]

Tq

[@Ash-pv5db]

Thanks man

[@johnmagdy4973]

I love you so much

[@amardhillon314]

Amazing

[@hoyinli7462]

could you please also upload your code to somewhere, like github? Thanks for your video anyway!

[@PrototypeHQ1]

anyone knows how to do it in reverse? the spiral instead of going inwards to go outwards

[@大盗江南]

Hi, how did u know that this is a microsoft problem？

[@KANISHKSAHUSIME]

god level

[@drakata27]

I fucking hate leetcode... thanks for the good explanation🙌