Merge Two Sorted Arrays

Question

Given two sorted arrays nums1 and nums2, merge them into a single sorted array.

Example:
Input: nums1 = [1,3,5], nums2 = [2,4,6]
Output: [1,2,3,4,5,6]

Follow-up: Can you do it in O(n) time complexity?

Accepted Answer

Solution for Merging Two Sorted Arrays:

1. Approach:
   - Use two pointers technique
   - Compare elements from both arrays
   - Build result array in sorted order

2. Code Implementation:
```python
def merge_sorted_arrays(nums1, nums2):
    result = []
    i = j = 0
    
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            result.append(nums1[i])
            i += 1
        else:
            result.append(nums2[j])
            j += 1
    
    # Add remaining elements
    result.extend(nums1[i:])
    result.extend(nums2[j:])
    
    return result
```

3. Time & Space Complexity:
   - Time: O(n + m) where n, m are lengths of input arrays
   - Space: O(n + m) for result array

4. Edge Cases:
   - Empty arrays
   - Arrays of different lengths
   - Duplicate elements
   - Negative numbers

5. Optimizations:
   - In-place merge if one array has extra space
   - Early termination if one array is exhausted
   - Handling special cases for small arrays

6. Testing:
```python
# Test cases
print(merge_sorted_arrays([1,3,5], [2,4,6]))  # [1,2,3,4,5,6]
print(merge_sorted_arrays([], [1,2,3]))       # [1,2,3]
print(merge_sorted_arrays([1], []))           # [1]
```

Company Context (Google):
- Focus on clean, efficient code
- Handle edge cases gracefully
- Consider scalability for large arrays
- Discuss potential optimizations

Merge Two Sorted Arrays

Question Explain

Answer Example

Related Interview Questions