Merge Two Sorted Arrays

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:

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:

# 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