Merge Sorted Array
01 · Problem
You are given two integer arrays sorted in non-decreasing order, nums1 and nums2, along with integers m and n.
Only the first m entries of nums1 are real values; it has length m + n, and its last n slots are placeholder zeros reserved for the merge. nums2 holds exactly n values.
Merge the real values of both arrays into a single array of length m + n sorted in non-decreasing order, and return it. Ideally, perform the merge in place inside nums1.
02 · Examples
nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
[1,2,2,3,5,6]
The real values are [1,2,3] and [2,5,6]; interleaving them in order gives [1,2,2,3,5,6].
nums1 = [1], m = 1, nums2 = [], n = 0
[1]
nums2 is empty, so the result is just the real part of nums1.
nums1 = [0], m = 0, nums2 = [1], n = 1
[1]
nums1 has no real values (its single 0 is a placeholder), so the result is nums2.
03 · Constraints
- 01nums1.length == m + n
- 02nums2.length == n
- 030 <= m, n <= 200
- 041 <= m + n <= 200
- 05-109 <= nums1[i], nums2[j] <= 109
04 · Optimal complexity
- Time
- O(m + n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.