88. Merge Sorted Array

LeetCode 88. Merge Sorted Array

Description

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

The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has a size equal to m + n such that it has enough space to hold additional elements from nums2.

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Constraints:

• nums1.length == m + n

• nums2.length == n

• 0 <= m, n <= 200

• 1 <= m + n <= 200

• -109 <= nums1[i], nums2[i] <= 109

Tags

Array, Two Pointers

Solution

Use two pointers i, j start from m - 1 at nums1 and n - 1 at nums2 respectively, and another pointer k is assigned to the last position of nums1. Compare nums1[i] and nums2[j] until one of both pointers is out of index. We move the larger one to the slot which k points to, and decrease k and the pointer of the larger one by 1 respectively. After this loop, we still need to check if there are remaining numbers in nums2 (we do not need to check nums1 because elements of nums1 are already in their place). We repeatedly assign nums2[j] to nums1[k] until j is out of index.

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(1)$

Code

func merge(nums1 []int, m int, nums2 []int, n int) {
	i, j, k := m-1, n-1, m+n-1
	for ; i >= 0 && j >= 0; k-- {
		if nums1[i] > nums2[j] {
			nums1[k] = nums1[i]
			i--
		} else {
			nums1[k] = nums2[j]
			j--
		}
	}
	for ; j >= 0; k-- {
		nums1[k] = nums2[j]
		j--
	}
}