educative.io

Educative

An alternative to Solution 1 for Merge Two Sorted Lists

I believe this solution would be easier to understand than the current one proposed in Solution1. It does have the same space and time complexity as it is using a new list to hold the sorted elements from both lists.

def merge_list_additional_list(lst1, lst2):
"""
Two pointer solution. We start the head of each list and continue until either one or both lists are exhausted.
Append the rest of the list to the merged list. O(m * n) if any of the list have a different length,
otherwise O(n^2) time and O(n + m) space
:param lst1:
:param lst2:
:return:
"""
i, j = 0, 0

merged_list = []

while i < len(lst1) and j < len(lst2):
    if lst1[i] > lst2[j]:
        merged_list.append(lst2[j])
        j += 1
    else:
        merged_list.append(lst1[i])
        i += 1

if i < len(lst1):
    merged_list += lst1[i:]

if j < len(lst2):
    merged_list += lst2[j:]

return merged_list
2 Likes

Thank you @Dragos1. This is a good solution.
Anum Hassan|Developer Advocate
educative.io

In this course section on merging two sorted lists. Isn’t this just as a efficient

def mergeList(list1, list2):
    n1,n2 = len(list1), len(list2)
    if n2> n1:
        list2.extend(list1) # O(n1)
        list2.sort() # O((n1 + n2) Log (n1 + n2))  = O(n Log n)
        return list2
    else:
        list1.extend(list2) # O(n2)
        list1.sort() # O((n1 + n2) Log (n1 + n2)) = O(n Log n)
        return list1

Which if n1 == n2 == n we have as O(n)

2 Likes

Wow, that’s great @Oti_Rowland.
Happy Learning at Educative :slight_smile:
Anum Hassan|Developer Advocate
Educative.io

1 Like

@Dragos1 nice solution. You can also remove the last two if statements by adding one extra condition in the first if statement.

def merge_lists(lst1, lst2):
   i, j = 0, 0
   result = []
   while i < len(lst1) and j < len(lst2) :
       if i < len(lst1) and lst1[i] < lst2[j]:
           result.append(lst1[i])
           i += 1
       else:
           result.append(lst2[j])
           j += 1
   return result

@Anum_Hassan

What about this?

    def merge_lists(lst1, lst2):
           lst1.extend(lst2)
           lst1.sort()
           return lst1

Does this valid?
def merge_lists(lst1,lst2):
return sorted(lst1+lst2)

this is the pythonic answer

Based on the posted solution it is unclear to me how a comparison is handled when the elements have the same value. For instance list1 = [0, 2, 4, 6] and list2 = [0, 10, 11, 12]. If comparing list1[0] < list2[0], you’re checking if 0 is less than 0, so how is this handled in the proposed solution?

Here’s my answer. It passed all the tests, although I am sure it is not optimal:

def merge_lists(lst1, lst2):
  # Write your code here
  new_list = lst1 + lst2
  length = len(new_list)
  counter = 0
  while counter < length-1:
    if new_list[counter] > new_list[counter + 1]:
      new_item = new_list[counter + 1]
      new_list.pop(counter + 1)
      new_list.insert(counter, new_item)
      counter = 0
    else:
      counter = counter + 1
  return new_list

Course: Educative: Interactive Courses for Software Developers
Lesson: Educative: Interactive Courses for Software Developers

had the same solution, and is it just me or it seems that suggested Solution 1 has kind of unnecessary overthinking with that 3rd list with placeholders? Why do you need to create a full list before, if you can just fill it on the go?


Course: Educative: Interactive Courses for Software Developers
Lesson: Educative: Interactive Courses for Software Developers

And also a remark about that comment by OP:

Why so? Time complexity is not O(n^2), we are traversing every array for one time only, it’s just O(M+N), or am I missing something?

fixed: wrote O(M*N) my mistake the 1st time, meant O(M+N)


Course: Educative: Interactive Courses for Software Developers
Lesson: Educative: Interactive Courses for Software Developers

You are correct it’s O(m*n) there is a single pass, however if m=n would that not be n2?

ah, haha, I actually made a mistake in that comment, I meant the complexity should be O(m + n) not O(m * n), no? We are going through each list just once, we are not going through each list several times depending on the size of another list, as it would be in some kind of “for loop inside of for loop”.

Even in the official solution it’s written that “The time complexity for this algorithm is O(n+m), where n and m are the lengths of the lists.