Trying to solve Leetcode problem 21 - Merge 2 sorted lists. Heres the problem below and my own attempt which dosen't work. If anyone can help explain to me the flaw in my logic because it dosen't work :(.
`var mergeTwoLists = function(list1, list2) {
const final = [];
for (let i=0; i<list1.length; i++) {
for (let j=0; j<list2.length; j++) {
if (list2[j] > list1[i]) {
final.push(list1[i]);
} else if (list1[i] > list2[j]) {
final.push(list2[j]);
} else if (list1[i] == list2[j]) {
final.push(list1[i], list2[j]);
}
}
}
return final;
};`
Top comments (9)
This is my idea how to solve this problem: jsfiddle.net/k6uoszvm/
Code:
Thanks for your solution! However, could you explain what the const insertIndex does? I dont understand the "x => x => item" part.
It's not
x => x => item
. It'sx => x >= item
. I can see source of confusion though. Maybe I should write other wayx => item <= x
.If you don't know this syntax, it's arrow function. I could write this with normal function:
Anyway, here is an alogirithm:
For each item in
listB
, I am looking for first item innewList
, that is bigger or equal and then insert item from list B before found.Example:
List A: 1 2 4
List B: 1 3 4
newList = [...listA] // [1, 2, 4]
Steps while iterating over
listB
:1
. First item in new list that is greater or equal is1
, which is at index0
.newList
at index 0[1, 1, 2, 4]
3
. First item in new list that is greater or equal is4
, which it at index3
.newList
at index 3[1, 1, 2, 3, 4]
4
. First item in new list that is grater or equal is4
which is at index4
.newList
at index 4[1, 1, 2, 3, 4, 4]
I hope I explained it better now.
I tried to solve it, here it is onecompiler.com/javascript/3y3uspame
var mergeTwoLists = function(list1, list2) {
const final = [];
let i=0, j=0;
for (; i if (list1[i] > list2[j]) {
final.push(list2[j]);
j++;
} else{
final.push(list1[i]);
i++
}
}
while(i<list1.length ){
final.push(list1[i]);
i++;
}
while(j<list2.length ){
final.push(list2[j]);
j++;
}
return final;
};
Also, is there a flaw in my logic for the code i first posted? I still don't understand why it is wrong.
Thanks for the solution! I don't understand line 10 and 11 though. If j is the counter for list2, why is i assigned as the index for list2 in these 2 lines?
You are running nested loop which is not useful in this case as the lists are sorted.
The idea here to loop both the list only once.
if the smaller element is in list1 then we will push the element in final list and increase counter i by 1 else push element from list2 and increase counter j by 1.
My suggestion would be try this with putting debugger or some logs in this logic so that you get more understanding.
Because the time complexity of above code is very high (i.e. 0(n^2)) that's why it is not accepting and which is also not preferable at interviews and interviewer will ask to optimize the code.
Here is the code you can use as the reference.
class Solution {
}