@@dineshsenthil1237 I know I'm a tad late but he means (I think) having one pointer that goes throughs and appends each element to the answer. I did it this way but its complexity isn't great. Here's my code if that helps explaining at all :) def mergeAlternately(self, word1, word2): p=0 ans = [] len1, len2 = len(word1), len(word2) while p < len1 or p < len2: if p < len1: ans.append(word1[p]) if p < len2: ans.append(word2[p]) p += 1 return ''.join(ans)
Would love and appreciate a video on all the basics concepts of data structures and algorithms and there uses. Would help lot of non cs students 🙏🙏 Edited: I think u already hav such videos like big O for coding interviews Need that kind of videos for DSA
Hi NeetCode, could you please explain why did you assess the time complexity as O(n + m), and not as O(Max(n,m). Because basically the algorithm will loop at max Math.Max(n, m) if we are using while with two conditions.
In this case we are iterating over both the strings atleast once in our while loop because we need all the characters from both strings combined.If we were asked to append only the alternating characters for eg. a="abcd", b="pqr" and result = "aqcd" then it would have been O(Max(m,n)).
another approach with time complexity O(m+n): "class Solution { public String mergeAlternately(String word1, String word2) { String ans = ""; int length1 = word1.length(); int length2 = word2.length(); int index = 0; for(int i = 0; i < length1; i++) { ans += word1.charAt(i); if(i == index && i
Same. But I think this may be a slightly more efficient version of yours: onesize = len(word1) twosize = len(word2) maxsize = max(onesize, twosize) x = "" for i in range(maxsize): if i < onesize: x += word1[i] if i < twosize: x += word2[i] return x
Try pre sizing the list. Bet that speeds it up a fair bit. Also one index. Better yet use c++, malloc the size of memory you need(+1 for the null terminator), the set the char at each memory address and return a const char* that points to the start of the string
In python strings are immutable (cannot be changed), instead a new string is created. So as you append a char, python copied your old string into a new string with 1 extra space where your char is appended. When you join a list I'm assuming it's a built-in function that will allocate memory required for the whole list.
You can use a single i and take from both strings at the same index, starting with word1, then at the end compare the lengths of the strings and take the rest of the longer one. The i,j way is done is similar to a Linked List problem where you would pick from two LL into a single LL and just concat at the end. I think the i,j way is less error prone and is the way I prefer doing it, also easily applicable to various LL problems.
You can do it with a single pointer as @patchouli said. I also prefer to use i and j though. I think it's clearer and it's a more general pattern. But if you do use a single pointer, you don't need to compare the lengths of the strings at the end. You can still use the slicing. The code is below. (And before anyone guesses that this won't work, yes I did submit this). class Solution: def mergeAlternately(self, word1: str, word2: str) -> str: i = 0 res = [] while i < len(word1) and i < len(word2): res.append(word1[i]) res.append(word2[i]) i += 1 res.append(word1[i:]) res.append(word2[i:]) return "".join(res)
Was asked a LC hard in an interview today that you covered.
Hoping the rest of the rounds go well, so thankful for the content.
Wc lc number?
Can you say which one?
which one?
Great video as always ,
I think One pointer will do the job we don't need two
could you explain ?
@@dineshsenthil1237 I know I'm a tad late but he means (I think) having one pointer that goes throughs and appends each element to the answer. I did it this way but its complexity isn't great. Here's my code if that helps explaining at all :)
def mergeAlternately(self, word1, word2):
p=0
ans = []
len1, len2 = len(word1), len(word2)
while p < len1 or p < len2:
if p < len1:
ans.append(word1[p])
if p < len2:
ans.append(word2[p])
p += 1
return ''.join(ans)
Would love and appreciate a video on all the basics concepts of data structures and algorithms and there uses. Would help lot of non cs students 🙏🙏
Edited: I think u already hav such videos like big O for coding interviews
Need that kind of videos for DSA
This was a simple and easy to understand solution. Thanks!
This was my solution
class Solution:
def mergeAlternately(self, word1: str, word2: str) -> str:
n1 = 0
n2 = 0
res = ''
while n1 < len(word1) or n2 < len(word2):
if n1 > len(word2) - 1:
res += word1[n1]
n1 += 1
continue
if n2 > len(word1) - 1:
res += word2[n2]
n2 += 1
continue
res += word1[n1] + word2[n2]
n1 += 1
n2 += 1
return res
Hi NeetCode, could you please explain why did you assess the time complexity as O(n + m), and not as O(Max(n,m). Because basically the algorithm will loop at max Math.Max(n, m) if we are using while with two conditions.
In this case we are iterating over both the strings atleast once in our while loop because we need all the characters from both strings combined.If we were asked to append only the alternating characters for eg. a="abcd", b="pqr" and result = "aqcd" then it would have been O(Max(m,n)).
go for the word with shorter length to loop and then concat what is left on the longer word
This is exactly what I did
another approach with time complexity O(m+n): "class Solution {
public String mergeAlternately(String word1, String word2) {
String ans = "";
int length1 = word1.length();
int length2 = word2.length();
int index = 0;
for(int i = 0; i < length1; i++) {
ans += word1.charAt(i);
if(i == index && i
class Solution:
def mergeAlternately(self, word1: str, word2: str) -> str:
output = ""
len1 = len(word1)
len2 = len(word2)
pointer1 = 0
pointer2 = 0
for i in range(len1+len2):
if pointer1 < len1:
output = output + word1[pointer1]
pointer1 = pointer1+1
if pointer2 < len2:
output = output + word2[pointer2]
pointer2 = pointer2 +1
return output
I did it such an unpythonic way
Same. But I think this may be a slightly more efficient version of yours:
onesize = len(word1)
twosize = len(word2)
maxsize = max(onesize, twosize)
x = ""
for i in range(maxsize):
if i < onesize:
x += word1[i]
if i < twosize:
x += word2[i]
return x
i solved it with a stringbuilder in java idk if that's a correct approach
Hey Neetcode, Can you please solve this problem 662. Maximum Width of Binary Tree?
How'd you know that was gonna be todays daily problem 😉
Why are you using two i and j counters when they are exactly the same? j can be removed completely and be replaced by i
Try pre sizing the list. Bet that speeds it up a fair bit. Also one index.
Better yet use c++, malloc the size of memory you need(+1 for the null terminator), the set the char at each memory address and return a const char* that points to the start of the string
Can anybody explain why converting string to list and then converting list to string is more efficient in python.
In python strings are immutable (cannot be changed), instead a new string is created.
So as you append a char, python copied your old string into a new string with 1 extra space where your char is appended.
When you join a list I'm assuming it's a built-in function that will allocate memory required for the whole list.
@@adama7752 thanks
Leetcode problem number 2096 please!!!
Do we need both i and j ?
You can use a single i and take from both strings at the same index, starting with word1, then at the end compare the lengths of the strings and take the rest of the longer one. The i,j way is done is similar to a Linked List problem where you would pick from two LL into a single LL and just concat at the end. I think the i,j way is less error prone and is the way I prefer doing it, also easily applicable to various LL problems.
You can do it with a single pointer as @patchouli said. I also prefer to use i and j though. I think it's clearer and it's a more general pattern.
But if you do use a single pointer, you don't need to compare the lengths of the strings at the end. You can still use the slicing. The code is below. (And before anyone guesses that this won't work, yes I did submit this).
class Solution:
def mergeAlternately(self, word1: str, word2: str) -> str:
i = 0
res = []
while i < len(word1) and i < len(word2):
res.append(word1[i])
res.append(word2[i])
i += 1
res.append(word1[i:])
res.append(word2[i:])
return "".join(res)
@@patchouli9 i did the LL way where I used 2 while loops to exhaust the remaining string
I have a question. Do Google know it is you(from your voice and such)
Aliens 👽👽 attendance taken by here
first