Spiral Matrix - Microsoft Interview Question - Leetcode 54

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Problem Link: neetcode.io/problems/spiral-m...
0:00 - Read the problem
1:10 - Drawing explanation
9:50 - Coding explanation
leetcode 54
This question was identified as a microsoft interview question from here: github.com/xizhengszhang/Leet...
#microsoft #matrix #python

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

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

[@shivanshsingh176]

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

[@rishikaverma9846]

absolutely love how you explain such complex problems with such clarity

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

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

[@NhanSleeptight]

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

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

[@nehabhavsar4943]

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

[@Anirudh-cf3oc]

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

[@Ben-pb7ct]

One of the best explanation. Thank you

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

[@salimzhulkhrni1610]

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

[@sooryaprakash6390]

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

[@sachinfulsunge9977]

You make it look so simple!

[@Roshan-xd5tl]

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

[@Oda3908]

Cannot imagine doing leetcode without NeetCode

[@abhilashsingh439]

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

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

[@bhardwajatul09]

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

[@MP-ny3ep]

Great explanation as always . Thank you.

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

[@roses7390]

This was super helpful. Thank you

[@mnchester]

amazing explanation!

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

[@aumrudhlalkumartj6343]

Great explanation. Thanks

[@ms3801]

Such a good explanation on this thank you

[@nikhilnagarapu3077]

Great Explanation!!

[@chandrakethans5835]

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

[@sannge6471]

Very easy to understand!

[@redietyishak8278]

Thanks, that helped a lot!!!

[@srikanthvelpuri2973]

great work from you keep it up

[@nikhildinesan5259]

Was doing the same ques just yesterday😊..

[@nguyenbach4710]

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

[@___vijay___]

great explanation!!

[@amritpatel6331]

Awesome explantion.

[@ThinkVerse88]

You made this dead easy Thankyou so much 😘

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

[@akhilchandra5935]

Thanks!

[@rohitkumarsinha876]

love your work bro'

[@user-zx6hw7xz1n]

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

[@maamounhajnajeeb209]

you made it easy, thanks man.

[@NeetCode]

Glad it helped!

[@aakashbhatia]

Good explanation

[@mohithadiyal6083]

Best explanation

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

[@utkarshashinde9167]

Thanks a lotttt it helped

[@netraamrale8119]

this is best channel

[@freesoul2677]

Thank you!!

[@riddle-master-ruben]

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

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

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

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

[@expansivegymnast1020]

Good video!

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

[@danielcarlossmd]

Thank you

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

[@Ash-pv5db]

Thanks man

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

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

[@shenzheng2116]

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

[@saichandu8178]

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

[@VaraPrasad0004]

Tq

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

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

[@ryanben3988]

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

[@sidazhong2019]

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

[@CST1992]

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

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

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

[@amardhillon314]

Amazing

[@chegehimself]

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

[@abhinavs2484]

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

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

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

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

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

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

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

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

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

[@KANISHKSAHUSIME]

god level

[@igoragoli]

I love you.

[@nikhilgoyal007]

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

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

[@_XY_]

👏👏

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

[@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; } };

[@user-oy4kf5wr8l]

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

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

[@dayanandraut5660]

line16 ? why did you add the condition there?

[@dayanandraut5660]

Also i wrote code in java, slightly with different logic. Got runtime as 0ms

[@sravanikatasani6502]

its because we are updating right and top values after the first two for loops inside the while loop , as the code inside while loops is executed sequentially, the actual constraint left

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

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

[@drakata27]

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

[@punjtcs]

public List spiralOrder(int[][] matrix) { List list = new ArrayList(); int left= 0; int right= matrix[0].length-1; int up=0; int down = matrix.length-1; while(list.size()

[@zr60]

No offense, but why are you explaning the criteria for the question for like 80% of the video. We know how a spiral moves. Please concentrate on how we're actually going to solve the problem.

[@juliaschmidt3645]

First time ever that I like my solution better than yours // shorter. class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: ROWS, COLS = len(matrix), len(matrix[0]) visited = {} dirs =[[0,1], [1,0], [0,-1], [-1,0]] i =0 row, col = 0, 0 sol = [matrix[row][col]] visited[(row, col)] = True while len(visited.keys()) < (ROWS* COLS): dr, dc = dirs[i%4] row, col = row+dr, col+dc # turning point reached if col == COLS or row == ROWS or row == -1 or col == -1 or (row, col) in visited: i+=1 row, col = row-dr, col-dc else: sol.append(matrix[row][col]) visited[(row, col)] = True return sol