{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Merge Sorted Array – Solution & Complexity

Interview solutions
/
Merge Sorted Array

Solution Walkthrough

  1. Step 1: Warm up with extra space and sorting

    • Copy the meaningful part of nums1 using nums1[:m] (or its language equivalent), then append all of nums2.
    • Sort the combined values and return them.
    • This is easy to write and reason about, but it spends extra memory and relies on a general sort, so it is not the optimal interview answer.
    def merge_sorted_array(nums1: list[int], m: int, nums2: list[int], n: int) -> list[int]:
    merged = nums1[:m] + nums2[:n]
    merged.sort()
    return merged

  2. Step 2: Fill from the end with three pointers

    • Keep i at the last meaningful value in nums1, j at the last value in nums2, and write at the final slot of nums1.
    • Compare nums1[i] and nums2[j], writing the larger one into nums1[write], then move that pointer backward.
    • Writing from the end prevents you from overwriting unfinished values in the front of nums1.
    • When one array runs out, copy any remaining nums2 values. If nums1 still has leftovers, they are already in the correct place.
    • This achieves the optimal O(m + n) time and O(1) extra space.
    def merge_sorted_array(nums1: list[int], m: int, nums2: list[int], n: int) -> list[int]:
    i = m - 1
    j = n - 1
    write = m + n - 1

    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[write] = nums1[i]
            i -= 1
        else:
            nums1[write] = nums2[j]
            j -= 1
        write -= 1

    return nums1

FAQ

See also

Practice Merge Sorted Array online (run code in the browser)3Sum solution (medium)3Sum Closest solution (medium)Sort Colors solution (medium)Combination Sum II solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?