Using += on strings creates new strings on each iteration in linear time and space. Might I suggest using a list and appending each character (constant amortised time/space), then converting to string before returning.
While less elegant, I feel like the solution to this problem where you assign a list for each row and move up and down while assigning each letter from the input to a given list is a bit more intuitive. It's less space efficient but I think it's good to learn as well
Even better use an array of size equal to string, then at each index store the level e.g 0,1,2,3... ,then create a hashmap for each level adding the strings , then add all the values to ans
if you were lucky enough to have done this problem in advance and got someone who chose this exact or slight variation of this problem or if you're Einstein, probability of the latter quite abysmal, no shade - just a reality, thanks for coming to my TedxTalk
class Solution { public: string convert(string s, int numRows) { if (numRows == 1) return s;
string ans = ""; for (int r = 0; r < numRows; r++) { int inc = 2 * (numRows-1); for (int i = r; i < s.length(); i += inc) { ans += s[i]; if (r > 0 && r < numRows-1 && i + inc - 2 * r < s.length()) { ans += s[i + inc - 2*r]; } } } return ans; } };
it's pretty funny though that instead of a straightforward simulation you wrote the formula that you know. good luck to come up with this formula in an interview
Dang, what timing, I was searching for your solution of this question today and couldn't find it. This question is little confusing to understand. Thanks for uploading!
In the Medium Playlist, 75-88 are the same as 89-102, I think you've added them twice by mistake. Thanks for coming in clutch with all your videos man, really do appreciate it.
Alternative solution (very similar solution): Each time the size of the the vertical plus diagonal is 2n-2 (excluding the top of the top diagonal) So we can consider numbers mod 2n-2. So 0 mod 2n-2 are the peaks 1 mod 2n-2 and -1 mod 2n-2 are the next row 2 mod 2n-2 and -2 mod 2n-2 are the next row and so on
i spend more than 5h on this problem and after i said to myself let your ego and go watch the solution i don't know what wrong with me maybe i didn't approch a problem the best way
Awesome... I think I got a little bit of tricked by the section 'pointer'. I made two vairables and switch the flag in every step and increase it by the first variable or the second variable depending on the flag. But this solution is much eaiser to read and simple... Thanks for uploading this video!
class Solution(object): def convert(self, s, numRows): """ :type s: str :type numRows: int :rtype: str """ if numRows==1 : return s n=k=0 l=[] for i in range(numRows): l.append([]) j=1 for i in s: l[n].append(i) if n==numRows-1: j=-1 elif n==0: j=1 n+=j r="" for i in range(numRows): r+="".join(l[i]) return r
Your solution seems quite unintuitive honestly 😅 I thought of doing something like this, where we simply appending to the corresponding array index each iteration let i = 0; let down = true; for (const letter of s) { arr[i].push(letter); if (i === numRows - 1) down = false; if (i === 0) down = true; i += down ? 1 : -1; } And at the end we concat all of them.
I think I got your question, and the thing is: we're getting the current character on `res += s[i];` and we check if there is a character between the current one, and the next one (the next one is the one that we jump every time).
I am not good at building algorithms just like you created for the above question. If question like this come I might be able to solve but how can I build algorithm building activity in myself?
Generally focusing on the shape of the V, focusing on the number decreasing by 2 every time we go down. Way to explain this in a circular way there bud. Anyway good video aside from that.
Hey! Your videos are great! Can you please solve leetcode problem 68 text justification ? It is a hard problem and has a 89.13% frequency of being asked.
I did this in 1 while loop (no nesting) single iteration, super simple. I came here after my submission like I always do. I think your solution is a bit complicated. Anyway keep up the good work. :) :)
Hey, i had a bit of confusion still can you help me out in explanation for 2nd and 3rd row you used formula as increment-2*rownumber, but in code you used + i I didn't catch that from where that "i" come from, so can you explain bit about it.
Tried this code with JavaScript based on Python and it just throws an error. Can anyone give me a clue as to what I'm missing cause I'm stumped. var convert = function(s, n) { if(n == 1) return s; let res = ''; for(let i=0; i
'L's and 'V's .....WTF? Honestly is this what goes on in your head??? I see x numbers of arrays and a couple of incremental/decremental processes to solve this simple problem (I prefer to user the term puzzle).
that uses extra O(s) space complexity and O(2s) time complexity total, which depending on your interviewer might not be what they want. I just got this problem today in an interview and coded your solution, but at the end of it they told me they wanted a one-pass solution which required the method shown above.
I created a second channel where I post the daily LC solutions 👉 www.youtube.com/@NeetCodeIO
In case you're interested!
Your explanation has built my logic design strongers.
this problem humbled me real quick 😅
Using += on strings creates new strings on each iteration in linear time and space. Might I suggest using a list and appending each character (constant amortised time/space), then converting to string before returning.
Thats exactly how I did it the first time (and it worked, beats 47% time and 72% space complexity).
While less elegant, I feel like the solution to this problem where you assign a list for each row and move up and down while assigning each letter from the input to a given list is a bit more intuitive. It's less space efficient but I think it's good to learn as well
I solved it with that method and while less space efficient it was faster then 90% of submissions surprisingly
Even better use an array of size equal to string, then at each index store the level e.g 0,1,2,3... ,then create a hashmap for each level adding the strings , then add all the values to ans
How can we come up with this type of solution in 45 min interview? 🤕
practice and luck
15 minutes*, its usually 2 questions per 45.
With Shit ton of practice....easy...
if you were lucky enough to have done this problem in advance and got someone who chose this exact or slight variation of this problem or if you're Einstein, probability of the latter quite abysmal, no shade - just a reality, thanks for coming to my TedxTalk
liked this video, disliked the leetcode problem
😂😂😂
Hi, I think if you move "increment = 2 * (numRows -1)" out of for loop may be better to understand. Still a really great solution! Thank you!
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) return s;
string ans = "";
for (int r = 0; r < numRows; r++) {
int inc = 2 * (numRows-1);
for (int i = r; i < s.length(); i += inc) {
ans += s[i];
if (r > 0 && r < numRows-1 && i + inc - 2 * r < s.length()) {
ans += s[i + inc - 2*r];
}
}
}
return ans;
}
};
If I had to answer this I would fail, just properly parsing the instructions felt difficult till I saw you draw the zig zag.
I Think this solution is really what comes to my head over the strings one, i couldn't break it down somehow. Thank you for the explanation
it's pretty funny though that instead of a straightforward simulation you wrote the formula that you know. good luck to come up with this formula in an interview
Dang, what timing, I was searching for your solution of this question today and couldn't find it. This question is little confusing to understand. Thanks for uploading!
Hey I just did this one. I bet your solution is 300x more elegant though
Edit: It is. :p
In the Medium Playlist, 75-88 are the same as 89-102, I think you've added them twice by mistake.
Thanks for coming in clutch with all your videos man, really do appreciate it.
Good catch, just fixed it
Alternative solution (very similar solution):
Each time the size of the the vertical plus diagonal is 2n-2 (excluding the top of the top diagonal)
So we can consider numbers mod 2n-2.
So 0 mod 2n-2 are the peaks
1 mod 2n-2 and -1 mod 2n-2 are the next row
2 mod 2n-2 and -2 mod 2n-2 are the next row
and so on
i spend more than 5h on this problem and after i said to myself let your ego and go watch the solution i don't know what wrong with me maybe i didn't approch a problem the best way
thanks Neetcode! I cant think of a use case when this would be needed in real life
Awesome... I think I got a little bit of tricked by the section 'pointer'. I made two vairables and switch the flag in every step and increase it by the first variable or the second variable depending on the flag. But this solution is much eaiser to read and simple... Thanks for uploading this video!
Someday i will understand how these geniuses find solutions
By the way i didn't understand solution
lol
Hi, Can you do Subsets 2? Couldn't find any good video for that problem. You explain every problem's solution nicely.
Hey can you do all top 100 questions of leetcode 🙂🙂
class Solution:
def convert(self, s: str, numRows: int) -> str:
n=len(s)
mat=[[""]*n for i in range(numRows)]
p,j=0,0
while(p
class Solution(object):
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
if numRows==1 : return s
n=k=0
l=[]
for i in range(numRows):
l.append([])
j=1
for i in s:
l[n].append(i)
if n==numRows-1: j=-1
elif n==0: j=1
n+=j
r=""
for i in range(numRows):
r+="".join(l[i])
return r
I saw this question and laughed at the discussion 😂
Your solution seems quite unintuitive honestly 😅
I thought of doing something like this, where we simply appending to the corresponding array index each iteration
let i = 0;
let down = true;
for (const letter of s) {
arr[i].push(letter);
if (i === numRows - 1) down = false;
if (i === 0) down = true;
i += down ? 1 : -1;
}
And at the end we concat all of them.
Thanks for your tutorial, I can't understand this question's solutions wrote by others until I watched this video.😂
nice explanation, but the initution of this problem is quite difficult when we see it for the first time
increment == 0 case:
increment = 2*(numRows-1) if 2*(numRows-1) > 0 else 1
Amazing Explanation man
Hi bro, one of your video starting with: "I am still unemployed, so lets leetcode" I am wondering if you are employed now
Good question, I wanna make a video about that soon 😉
increment should be outside the loop
In the nrw UI they have hidden the dislikes count. I don't know why. That's so wrong.
how does each element in res get to the right position yet they are generated by two different conditions
I think I got your question, and the thing is: we're getting the current character on `res += s[i];` and we check if there is a character between the current one, and the next one (the next one is the one that we jump every time).
Can you explain the algorithm of (numRows - 1) * 2?
I was thinking on this problem since yesterday and just realised that I confused rows and columns
I am not good at building algorithms just like you created for the above question. If question like this come I might be able to solve but how can I build algorithm building activity in myself?
oh shit i had something like this at my current job, i think i had to take the string and print the zigzag
Generally focusing on the shape of the V, focusing on the number decreasing by 2 every time we go down. Way to explain this in a circular way there bud. Anyway good video aside from that.
This problem gave me headaches real fast and imposter syndrome kicked in
Hey! Your videos are great! Can you please solve leetcode problem 68 text justification ? It is a hard problem and has a 89.13% frequency of being asked.
thank you so much!!
Oh man how did you think up the solution to this???!!
Please do a dry run of the code
I did this in 1 while loop (no nesting) single iteration, super simple. I came here after my submission like I always do. I think your solution is a bit complicated. Anyway keep up the good work. :) :)
once post your solution brother, it would be very helpful :)
I dont understand how solve this task without nesting loops. Pls, give me hint or solution, share some knowledge with coders brotherhood, man.
asked me in oracle interview with expected time 10 to 15 minutes, worst problem
How did you setup this dark theme on leetcode ?
Go to editor settings
you should make a replica video to all of your videos except made for c++ users
i love this channel
Hey, i had a bit of confusion still can you help me out
in explanation for 2nd and 3rd row you used formula as increment-2*rownumber, but in code you used + i I didn't catch that from where that "i" come from, so can you explain bit about it.
The sequence is 1 2 3 4 3 2 1 2 3 4… given the number of rows is 4, but can someone help me generate that sequence using a loop statement?
Tried this code with JavaScript based on Python and it just throws an error. Can anyone give me a clue as to what I'm missing cause I'm stumped.
var convert = function(s, n) {
if(n == 1) return s;
let res = '';
for(let i=0; i
amazing solution
legendary answer bruhhhhhh
One of the worst and useless problems out there. Adds nothing of value.
u r smart bro
So clean thought process👏
Can someone explain the "if" part please?
I hate this question!!
THANK-FUCKING-YOU!!!
TYSM
O(n.n/2)=======O(n^2) if i am wring correct me
It's o(n)
'L's and 'V's .....WTF? Honestly is this what goes on in your head??? I see x numbers of arrays and a couple of incremental/decremental processes to solve this simple problem (I prefer to user the term puzzle).
that uses extra O(s) space complexity and O(2s) time complexity total, which depending on your interviewer might not be what they want. I just got this problem today in an interview and coded your solution, but at the end of it they told me they wanted a one-pass solution which required the method shown above.
zhina
M
thanks man helped a lot!