⚡Flashcard Drill➔
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.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Two Pointers Problems

中文速览与面试要点

合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n,分别表示 nums1 和 nums2 中的元素数目。请你合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。注意:最终合并后数组不应由函数返回,而是存储在数组 nums1 中。nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0,应忽略。约束:nums1.length == m + n;nums2.length == n;0 ≤ m, n ≤ 200;1 ≤ m + n ≤ 200。

核心要点

  • 从后往前填充(标准解) :用三个指针——i 指向 nums1 的有效末尾(m−1)、j 指向 nums2 的末尾(n−1)、k 指向 nums1 的最终末尾(m+n−1)。
  • 比较并放置 :每次比较 nums1[i] 与 nums2[j] ,把较大者放到 nums1[k] ,然后相应指针左移。
  • 为什么必须从后往前 :从前往后填充会覆盖 nums1 中尚未处理的元素。从后往前则只会写入「已处理过的位置」,不会破坏未处理数据。
  • 循环条件只需 j &gt;= 0 :当 nums2 全部放完后,nums1 剩余的前缀本来就在正确位置,无需再动。

常见陷阱

  • 从前往后填充 :会覆盖 nums1 中尚未处理的元素。必须从后往前。
  • 循环条件写成 while i &gt;= 0 and j &gt;= 0 :这样当 nums1 先耗尽时会提前退出,遗漏 nums2 的剩余元素。正确条件是只看 j &gt;= 0 。
  • 忘记 i &gt;= 0 的边界判断 :当 nums1 的有效部分已全部移走后, nums1[i] 会越界(负下标会静默索引到末尾)。
  • 比较用 &gt;= :用 &gt; 或 &gt;= 在本题都不影响正确性(相等时先放哪个都一样),但 &gt; 更符合「严格大于才取 nums1」的直觉。

参考实现

class Solution:
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        i = m - 1               # nums1 有效部分的末尾
        j = n - 1               # nums2 的末尾
        k = m + n - 1           # nums1 的最终末尾
        while j >= 0:           # nums2 放完即可结束
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1
        # nums2 全部放入后,nums1 剩余前缀已在正确位置,无需处理