Problem overview
The method merge receives two lists of integers, first and second, each already sorted in ascending order. It returns one new sorted list that contains every number from both. Duplicates are kept: with first = [1, 4, 8] and second = [1, 3, 4, 17] the result is [1, 1, 3, 4, 4, 8, 17].
If the lengths are n and m, the lesson asks for O(n + m) time and O(n + m) extra space, the space being the result list itself.
Approach: two pointers
The simple way to merge two sorted lists in Python is to join them and sort: sorted(first + second). That is correct, but it ignores the fact that both inputs are already sorted, and in general sorting costs O((n + m) log (n + m)). The two-pointer merge uses the order to do the job in a single pass.
Keep one pointer in each list, i in first and j in second, both starting at 0. Because each list is sorted, the smallest number not yet used is one of the two numbers under the pointers. Compare them, copy the smaller one to the result, and move only that pointer forward. Repeat until one list is used up. At that point the other list holds only numbers that are at least as large as everything copied, in order, so you copy what is left.
On the example: 1 against 1 copies the second 1 (a tie goes to second in this solution), then 1 against 3 copies the 1 from first, 4 against 3 copies 3, 4 against 4 copies the 4 from second, 4 against 17 copies the 4 from first, and 8 against 17 copies 8. Now first is used up, and the remaining 17 is copied from second.
Why is it safe to move only one pointer? Suppose first[i] is smaller than second[j]. Everything after second[j] is at least as large as it, and everything after first[i] is at least as large as first[i] itself, so no unused number can be smaller than first[i]. It is therefore the next number in the merged order, and taking it never has to be undone.
Step by step
- Create the empty list
resultthat will hold the answer. - Set up the pointers:
i = j = 0assigns 0 to both names. - Loop while both lists have numbers left:
while i < len(first) and j < len(second). The loop stops as soon as one list is exhausted. - Compare the two current numbers. If
first[i] < second[j], appendfirst[i]and incrementi. - Otherwise append
second[j]and incrementj. Equal numbers land here. - Copy the rest of
firstwith a secondwhile i < len(first)loop that appends and increments. - Copy the rest of
secondwith a third loop onj. At most one of these two loops runs, since the first loop ended because a list was used up. - Return
result.
The solution in Python
class Solution:
def merge(self, first: List[int], second: List[int]) -> List[int]:
result = []
i = j = 0
while i < len(first) and j < len(second):
if first[i] < second[j]:
result.append(first[i])
i += 1
else:
result.append(second[j])
j += 1
while i < len(first):
result.append(first[i])
i += 1
while j < len(second):
result.append(second[j])
j += 1
return result
Python details:
- The inputs are not changed. The method only reads
firstandsecondand builds a new list, so the caller's lists stay as they were. appendis cheap. Appending to the end of a list takes constant time on average, which keeps the whole merge linear. Inserting at the front would not.- Standard library shortcuts.
sorted(first + second)is the shortest way.heapq.merge(first, second)does the same two-pointer merge lazily and returns an iterator, so wrap it inlist()to get a list. Both give[1, 1, 3, 4, 4, 8, 17]for the example. Writing the loops yourself is the point of the lesson, and the pattern carries over to other merging problems.
Complexity
Every iteration of the three loops appends exactly one number and advances one pointer. The pointers never move back, and there are n + m numbers in total, so the time is O(n + m). The result holds n + m numbers, so the extra space is O(n + m). Merging without an extra list is a different, harder problem.
Edge cases and common mistakes
- One list is empty.
merge([], [2, 3])skips the first loop and copiessecondin the last loop, giving[2, 3]. The same holds the other way round, and two empty lists give[]. - All of one list is smaller.
merge([1, 2], [5, 6])uses upfirstfirst, and the final loop copies[5, 6]. With the arguments swapped the result is the same,[1, 2, 5, 6]. - Duplicates. Equal numbers are all kept. Which list a tie is taken from does not change the result of plain integers; it would matter for objects sorted by a key.
- Negative numbers. Nothing special:
merge([-3, 0], [-5, -1, 2])gives[-5, -3, -1, 0, 2]. - Forgetting the leftover loops. Without them, any numbers remaining after the first loop are dropped. In the example the 17 would be lost.
- Forgetting to advance a pointer. If
i += 1orj += 1is missing, the loop never ends.
Testing
[1, 4, 8]and[1, 3, 4, 17]give[1, 1, 3, 4, 4, 8, 17].[]and[2, 3]give[2, 3].[5, 6]and[1, 2]give[1, 2, 5, 6].[-3, 0]and[-5, -1, 2]give[-5, -3, -1, 0, 2].
