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!
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).
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 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?
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.
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 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! 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.
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.
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.
