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_
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.
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 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 :/
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
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
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.
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
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]
*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?
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
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?
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 };
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.
@@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.
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.
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?
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).
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.
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.
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.
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.
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
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.
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
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?
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
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
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
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; } };
🚀 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!
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.
He missed explanation of the only real edge case that gets people. "Trust me bro", not very neetcode is it?
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/
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 was having a hard time understanding from the discussion section, but understood it immediately by watching your video.
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
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
I used an array of directions and modulo four'd it
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.
Happy Teacher's day man ! Specifically chose a old video to comment because they were helpful to me .
Thank you for your contribution.
Cannot imagine doing leetcode without NeetCode
Thank you so much for the explanation. I want to do leetcode every day with your videos
Thanks!
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
this was a great explanation! I loved the drawings and the step by step walkthrough in the beginning. And you spoke so clearly too :)
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]
*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?
the break looks more clean, this is ugly
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
Your answer is always clear and concise. The universities should hire more teachers like you, not PPT readers like my professors :).
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
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?
absolutely love how you explain such complex problems with such clarity
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.
One of the best explanation. Thank you
With this, I was able to solve spiral matrix 1,2 and 4
Your videos are absolutely amazing! Thank you so much!
Jesus the way u make everything easier is so gud thanks a lot
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.
@@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.
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.
Was doing the same ques just yesterday😊..
Very well explained.... Your video made this complex problem very easy 👏👏👏👏
Clear and simple explanation as always. Thank you so much!
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?
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 so much was scared of this question earlier not anymore
Great, clear explanation, as ALWAYS!! Thank you SO much!!
I was doing that in quite confusive and unclear way) more mathematical) but your way is much better)
We can use DFS with order Right, Down, Left, Up
Clear and simple explanation. Keep up the great work as always sir! :)
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
came here at 8/824 as a lc daily challenge was spiral 3,so came to 1 and going 2 from her till 3rd
Thank you so much..i was stuck in this problem for more than an hour
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
Great explanation as always . Thank you.
amazing explanation!
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.
Great and amazing explanation as always. Thank you!! Cheers :)
I got a "96% faster" with this solution, thanks!
Was missing out line 17 and 18😂😂 test case [[1,2,3]] was literally killing me, I almost hard coded it
You made this dead easy Thankyou so much 😘
A BIG Thanks ❤️
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.
shouldnt line 23 be jus top instead of top -1? u dont want to include top -1 element since its has been added above
Very easy to understand!
This was super helpful. Thank you
i think there should be || instead of && at line 16 because at GFG it is not accepting if i put a && operator over there
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.
this is best channel
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
got this qsrtn asked at Microsoft recently, I gave a recursive solution
Such a good explanation on this thank you
Great explanation. Thanks
Great Explanation!!
Awesome explantion.
great explanation!!
you made it easy, thanks man.
Glad it helped!
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.
Thanks, that helped a lot!!!
Thank you
Best explanation
great work from you keep it up
Banger
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
for i in range(right-1,left-1,-1):
same as:
for i in reversed(range(left,right)):
easier to understand.
Why is this not working for line 16?
_if right < left and bottom < top:_
_break_
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
Thanks a lotttt it helped
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?
Good explanation
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
Good video!
love your work bro'
Thank you!!
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.
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
note to self - corner cells did not get added twice since top pointer changed.
Thanks man
Tq
I love you.
I love you so much
Amazing
anyone knows how to do it in reverse? the spiral instead of going inwards to go outwards
could you please also upload your code to somewhere, like github?
Thanks for your video anyway!
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
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
god level
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;
}
};
Hi, how did u know that this is a microsoft problem？