Leetcode 21. Merge Two Sorted Lists

Problem

You are given two sorted arrays of integers in ascending order. Your task is to merge these two arrays into a single sorted array that contains all elements from both input arrays while maintaining the ascending order.

Both input arrays are already sorted, and your solution should take advantage of this property to efficiently combine them.

Requirements

1. Merge both arrays into a single sorted array
2. Maintain ascending order in the result
3. Include all elements from both input arrays (duplicates should be preserved)
4. Handle edge cases where one or both arrays are empty

Constraints

• 0 ≤ list1.length, list2.length ≤ 50
• -100 ≤ list1[i], list2[i] ≤ 100
• Both list1 and list2 are sorted in ascending order
• Aim for O(n + m) time complexity where n and m are the lengths of the two arrays

Examples

Example 1:

Input: list1 = [1, 2, 4], list2 = [1, 3, 4] Output: [1, 1, 2, 3, 4, 4] Explanation: Merging the two sorted arrays results in [1, 1, 2, 3, 4, 4]

Example 2:

Input: list1 = [], list2 = [0] Output: [0] Explanation: When one array is empty, the result is the other array

Example 3:

Input: list1 = [], list2 = [] Output: [] Explanation: Two empty arrays produce an empty result

Example 4:

Input: list1 = [1, 3, 5], list2 = [2, 4, 6] Output: [1, 2, 3, 4, 5, 6] Explanation: Elements are interleaved to maintain sorted order

Hint 1: Two Pointer Approach Since both arrays are already sorted, you can use two pointers—one for each array. At each step, compare the elements at both pointers and add the smaller one to your result, then advance that pointer.

Hint 2: Handling Remaining Elements After one array is fully processed, don't forget to append all remaining elements from the other array to your result. Since both arrays are sorted, all remaining elements will be greater than what you've already added.

Hint 3: Edge Cases Consider what happens when one or both arrays are empty. These cases should be handled at the beginning of your solution for efficiency.

Full Solution ` def mergeTwoLists(list1, list2): # Handle edge cases where one or both lists are empty if not list1: return list2 if not list2: return list1

# Initialize result array and two pointers
result = []
i, j = 0, 0

# Compare elements from both lists and add the smaller one
while i < len(list1) and j < len(list2):
    if list1[i] <= list2[j]:
        result.append(list1[i])
        i += 1
    else:
        result.append(list2[j])
        j += 1

# Add remaining elements from list1 (if any)
while i < len(list1):
    result.append(list1[i])
    i += 1

# Add remaining elements from list2 (if any)
while j < len(list2):
    result.append(list2[j])
    j += 1

return result

`

Explanation:

The solution uses a two-pointer approach to efficiently merge the sorted arrays:

1. Edge Case Handling: First, we check if either array is empty and return the other array if so.
2. Two Pointers: We maintain two pointers, i for list1 and j for list2, both starting at index 0.
3. Comparison Loop: While both pointers are within their respective array bounds, we compare the elements at these positions. We add the smaller element to our result and advance the corresponding pointer.
4. Remaining Elements: After one array is exhausted, we append all remaining elements from the other array. Since both arrays are sorted, these remaining elements are guaranteed to be larger than everything already in the result.

Time Complexity: O(n + m) where n and m are the lengths of list1 and list2. We visit each element exactly once.

Space Complexity: O(n + m) for the result array. If you don't count the output array, the space complexity is O(1) as we only use a constant amount of extra space for the pointers.

Alternative Approach: You could also use Python's built-in functions like sorted(list1 + list2), but this would have O((n+m) log(n+m)) complexity and wouldn't take advantage of the fact that the input arrays are already sorted.