💬 Discord
Sign In
NeetCode #181LC-88EasyTwo PointersNC 250
← Back to All Problems

#181 · #88 · Merge Sorted Array(合并两个有序数组)

📌 Problem Statement & Constraints

You are given two sorted integer arrays nums1 and nums2 and two integers m and n, where nums1 has length m + n with the first m elements being the real data and the last n slots empty. Merge nums2 into nums1 in place, keeping it sorted. Constraints: 0 <= m, n <= 200, nums1.length == m + n.

💡 Core Algorithmic Approaches

  1. The naive approach copies nums1 and merges from the front, which needs O(m) extra space.
  2. Merge from the back instead: the largest element among the current ends goes to the last free slot.
  3. This works because nums1 has exactly n trailing free slots, so writing backwards never overwrites unprocessed data.
  4. After the loop, only nums2 may have leftovers, which are copied directly. Any leftover of nums1 is already in place.

💻 Benchmark Python3 Implementation

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i = m - 1                      # last real element of nums1
        j = n - 1                      # last element of nums2
        k = m + n - 1                  # last slot of nums1
        while i >= 0 and j >= 0:
            if nums1[i] > nums2[j]:
                nums1[k] = nums1[i]    # larger goes to the back
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1
        # only nums2 can have leftovers; nums1's are already in place
        while j >= 0:
            nums1[k] = nums2[j]
            j -= 1
            k -= 1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m + n): each element is written once.
💾 Space Complexity
O(1): the merge happens entirely inside nums1.

⚠️ Interview Pitfalls & Follow-ups

  • Merging from the front: you would overwrite unprocessed elements of nums1, requiring a copy of the first m elements and O(m) extra space.
  • Forgetting to copy the leftover nums2 elements: they must be placed, whereas leftover nums1 elements are already correct.
  • Using the > comparison in the wrong direction: the largest element goes to the back, so the comparison selects the larger.
  • Returning nums1: the signature returns None; the merge is in place.