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
- The naive approach copies
nums1and merges from the front, which needs O(m) extra space. - Merge from the back instead: the largest element among the current ends goes to the last free slot.
- This works because
nums1has exactlyntrailing free slots, so writing backwards never overwrites unprocessed data. - After the loop, only
nums2may have leftovers, which are copied directly. Any leftover ofnums1is 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 firstmelements and O(m) extra space. - Forgetting to copy the leftover
nums2elements: they must be placed, whereas leftovernums1elements 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 returnsNone; 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.
🧩 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 >= 0 :当 nums2 全部放完后,nums1 剩余的前缀本来就在正确位置,无需再动。
常见陷阱
- 从前往后填充 :会覆盖 nums1 中尚未处理的元素。必须从后往前。
- 循环条件写成 while i >= 0 and j >= 0 :这样当 nums1 先耗尽时会提前退出,遗漏 nums2 的剩余元素。正确条件是只看 j >= 0 。
- 忘记 i >= 0 的边界判断 :当 nums1 的有效部分已全部移走后, nums1[i] 会越界(负下标会静默索引到末尾)。
- 比较用 >= :用 > 或 >= 在本题都不影响正确性(相等时先放哪个都一样),但 > 更符合「严格大于才取 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 剩余前缀已在正确位置,无需处理