Spiral Matrix - Microsoft Interview Question - Leetcode 54
Vložit
- čas přidán 5. 07. 2024
- 🚀 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 - Věda a technologie
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
It's a good platform.. thanks to you.
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_
Nice Observation
Superb logic
I think he wanted to keep left and right border logic consistent
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.
Thank you for the kind words, it means a lot!
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 :/
Huh never thought about doing that
wow it was probably your interviewer who was just being dumb
I have no ideas. Can you explain more/
I was having a hard time understanding from the discussion section, but understood it immediately by watching your video.
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
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
absolutely love how you explain such complex problems with such clarity
Thank you so much for the explanation. I want to do leetcode every day with your videos
Happy Teacher's day man ! Specifically chose a old video to comment because they were helpful to me .
Thank you for your contribution.
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
Cannot imagine doing leetcode without NeetCode
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
This is so much better
this was a great explanation! I loved the drawings and the step by step walkthrough in the beginning. And you spoke so clearly too :)
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
Clear and simple explanation. Keep up the great work as always sir! :)
Clear and simple explanation as always. Thank you so much!
Great, clear explanation, as ALWAYS!! Thank you SO much!!
One of the best explanation. Thank you
Great and amazing explanation as always. Thank you!! Cheers :)
Thank you so much..i was stuck in this problem for more than an hour
Very well explained.... Your video made this complex problem very easy 👏👏👏👏
You make it look so simple!
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).
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.
Thank you so much was scared of this question earlier not anymore
Great explanation as always . Thank you.
This was super helpful. Thank you
Such a good explanation on this thank you
Was doing the same ques just yesterday😊..
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
};
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.
amazing explanation!
Jesus the way u make everything easier is so gud thanks a lot
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]
Great explanation. Thanks
Great Explanation!!
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.
I was doing that in quite confusive and unclear way) more mathematical) but your way is much better)
Thanks, that helped a lot!!!
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.
With this, I was able to solve spiral matrix 1,2 and 4
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?
You made this dead easy Thankyou so much 😘
great work from you keep it up
Very easy to understand!
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.
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?
Your answer is always clear and concise. The universities should hire more teachers like you, not PPT readers like my professors :).
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?
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
great explanation!!
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?
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.
Awesome explantion.
Thanks!
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
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.
Why is this not working for line 16?
_if right < left and bottom < top:_
_break_
Was missing out line 17 and 18😂😂 test case [[1,2,3]] was literally killing me, I almost hard coded it
love your work bro'
i think there should be || instead of && at line 16 because at GFG it is not accepting if i put a && operator over there
you made it easy, thanks man.
Glad it helped!
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
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!
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.
Good explanation
Good video!
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?
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.
@@NeetCode thank you so much for the kind reply. I just subscribe you. Again, I appreciate it ! It really helps me a lot
this is best channel
Thank you!!
Best explanation
Thanks a lotttt it helped
could you please also upload your code to somewhere, like github?
Thanks for your video anyway!
Thanks man
anyone knows how to do it in reverse? the spiral instead of going inwards to go outwards
Thank you
We can use DFS with order Right, Down, Left, Up
Is the time complexity for this question O(min(m, n)*max(m, n)) ? and the space complexity O(m*n)
The time complexity is O(m*n) because every value is looked at
I got a "96% faster" with this solution, thanks!
Amazing
for i in range(right-1,left-1,-1):
same as:
for i in reversed(range(left,right)):
easier to understand.
What would be the complexity here? I am guessing o(M) is time and o(m) is the space as well?
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
@@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)
@@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.
got this qsrtn asked at Microsoft recently, I gave a recursive solution
*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
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?
Tq
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?
note to self - corner cells did not get added twice since top pointer changed.
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.
Hi, how did u know that this is a microsoft problem？
👏👏
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
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
god level
line16 ? why did you add the condition there?
Also i wrote code in java, slightly with different logic. Got runtime as 0ms
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
I love you.
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;
}
};
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
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
return matrix and [*matrix.pop(0)] + self.spiralOrder([*zip(*matrix)][::-1])
copied!
Thanks for showing the world your garbage code
I fucking hate leetcode... thanks for the good explanation🙌
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()
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.
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