LeetCode 88: Merge Sorted Array (Two Pointers from Back)
LeetCode 88ArrayTwo PointersIn-placeToday we solve LeetCode 88 - Merge Sorted Array.
Source: https://leetcode.com/problems/merge-sorted-array/
English
Problem Summary
You are given nums1 of length m + n, where the first m elements are sorted valid numbers and the last n slots are zeros as buffer. nums2 has n sorted elements. Merge nums2 into nums1 so that nums1 becomes one sorted array in-place.
Key Insight
If we merge from the front, we overwrite values in nums1 that we still need. The safe strategy is to merge from the back. Compare the largest remaining values from both arrays and place the larger one at the end pointer.
Brute Force and Why Insufficient
One approach is copying all valid values to a new array, sorting, and writing back. That works but wastes extra memory and misses the in-place intention.
Optimal Algorithm (Step-by-Step)
1) Set pointers: i = m - 1 (end of valid nums1), j = n - 1 (end of nums2), k = m + n - 1 (write position).
2) While j >= 0:
• If i >= 0 and nums1[i] > nums2[j], write nums1[k] = nums1[i], decrement i.
• Else write nums1[k] = nums2[j], decrement j.
• Decrement k.
3) Done. If nums2 is exhausted, nums1 is already correct; if nums1 is exhausted first, remaining nums2 are copied by the loop.
Complexity Analysis
Time: O(m+n).
Space: O(1) extra.
Common Pitfalls
- Merging from front and corrupting unread nums1 values.
- Using condition i > 0 instead of i >= 0.
- Forgetting loop condition should be based on j (nums2 remaining).
- Not handling m = 0 edge case.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1;
int j = n - 1;
int k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
}
}func merge(nums1 []int, m int, nums2 []int, n int) {
i, j, k := m-1, n-1, m+n-1
for j >= 0 {
if i >= 0 && nums1[i] > nums2[j] {
nums1[k] = nums1[i]
i--
} else {
nums1[k] = nums2[j]
j--
}
k--
}
}class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
}
};from typing import List
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
i, j, k = m - 1, n - 1, m + n - 1
while j >= 0:
if i >= 0 and nums1[i] > nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1var merge = function(nums1, m, nums2, n) {
let i = m - 1;
let j = n - 1;
let k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
};中文
题目概述
给定 nums1（长度为 m+n，前 m 个是有效有序元素，后 n 个是占位 0）和有序数组 nums2（长度 n），要求把 nums2 合并进 nums1，并保持整体有序，且必须原地完成。
核心思路
从前往后合并会覆盖 nums1 里还没比较的值。正确做法是从后往前放：每次比较两边当前最大值，把更大的填到末尾指针 k。
暴力解法与不足
把有效元素全拷贝出来再排序，逻辑简单但需要额外空间，不符合本题“原地合并”的设计重点。
最优算法（步骤）
1）初始化三个指针：i=m-1，j=n-1，k=m+n-1。
2）当 j >= 0 时循环：
• 若 i >= 0 且 nums1[i] > nums2[j]，则写入 nums1[k]=nums1[i]，i--。
• 否则写入 nums1[k]=nums2[j]，j--。
• 每轮 k--。
3）循环结束即完成合并。
复杂度分析
时间复杂度：O(m+n)。
空间复杂度：O(1) 额外空间。
常见陷阱
- 从前往后写，导致未处理数据被覆盖。
- 条件误写成 i > 0，漏掉下标 0。
- 循环条件写错，应该盯 j（nums2 是否处理完）。
- 没考虑 m=0 的边界。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1;
int j = n - 1;
int k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
}
}func merge(nums1 []int, m int, nums2 []int, n int) {
i, j, k := m-1, n-1, m+n-1
for j >= 0 {
if i >= 0 && nums1[i] > nums2[j] {
nums1[k] = nums1[i]
i--
} else {
nums1[k] = nums2[j]
j--
}
k--
}
}class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
}
};from typing import List
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
i, j, k = m - 1, n - 1, m + n - 1
while j >= 0:
if i >= 0 and nums1[i] > nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1var merge = function(nums1, m, nums2, n) {
let i = m - 1;
let j = n - 1;
let k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
};
Comments