Reference: LeetCode
Difficulty: Easy

Problem

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

• The number of elements initialized in nums1 and nums2 are m and n respectively.
• You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Follow up: Can you solve in $O(N)$ without extra space?

Analysis

Merge and Sort

Time: $O((m + n)\log{(m + n)})$
Space: $O(1)$

Two Pointers

Like merging two sorted linked list, we can loop over from the beginning of the array. It turns out that we need an extra array of size $m$.

We can start from the end of two arrays and append elements from the right side.

Note: Prefer while-loop to for-loop.

Time: $O(m + n)$
Space: $O(1)$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.
Info
Article :
50
Total Count :
82.3k
UV :
PV :
Last Push :