[LeetCode][88. Merge Sorted Array] 3 Approaches: Sorting, Two Pointers and Reverse Two Pointers

By Long Luo

This article is the solution 3 Approaches: Sorting, Two Pointers and Reverse Two Pointers of Problem 88. Merge Sorted Array.

Here shows 3 Approaches to slove this problem: Sorting, Two Pointers and Reverse Two Pointers.

Sorting

Let the array nums2\textit{nums}_2 into the rear of array nums1\textit{nums}_1, and then sort the entire array.

1
2
3
4
5
6
7
public static void merge_sort(int[] nums1, int m, int[] nums2, int n) {
for (int i = 0; i < n; i++) {
nums1[m + i] = nums2[i];
}

Arrays.sort(nums1);
}

Analysis

  • Time Complexity: O((m+n)log(m+n))O((m + n)log(m+n)).
  • Space Complexity: O(log(m+n))O(log(m+n)).

Two Pointers

Since two arrays nums1\textit{nums}_1 and nums2\textit{nums}_2 are both sorted in non-decreasing order, so we can use the Two Pointers method.

We consider the two arrays as two queues, takes the smaller numbers from the two arrays headers each round and put it into our results.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static void merge(int[] nums1, int m, int[] nums2, int n) {
if (nums2 == null || nums2.length <= 0) {
return;
}

int[] num = new int[m + n];
int idx1 = 0;
int idx2 = 0;
int idx = 0;
while (idx < m + n) {
if (idx1 < m && idx2 < n && nums1[idx1] <= nums2[idx2]) {
num[idx++] = nums1[idx1++];
} else if (idx1 < m && idx2 < n && nums1[idx1] > nums2[idx2]) {
num[idx++] = nums2[idx2++];
} else if (idx1 == m && idx2 < n) {
num[idx++] = nums2[idx2++];
} else if (idx2 == n && idx1 < m) {
num[idx++] = nums1[idx1++];
}
}

for (int i = 0; i < m + n; i++) {
nums1[i] = num[i];
}
}

Analysis

  • Time Complexity: O(m+n)O(m + n).
  • Space Complexity: O(m+n)O(m + n).

Reverse Two Pointers

Since the extra space of nums1\textit{nums}_1 is in the back, it’s better to process the sorted data from the back to the front, fill in the values while traversing the array.

Let two pointers len1len1 and len2len2 to point to the tails of nums1nums1 and nums2nums2, traversal from the tail and compare the values, and set the pointer lenlen to point to the end of nums1\textit{nums}_1. After each traversal of the size of the comparison value, it will be filled.

When len1<0len1 \lt 0, the traversal ends. If the data of nums2\textit{nums}_2 is not copied completely, we can copy the rest to the front of nums1\textit{nums}_1, and finally we got the answer.

The process is show as the following images.

88 1

88 2

88 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public static void merge(int[] nums1, int m, int[] nums2, int n) {
int p = m - 1;
int q = n - 1;
int idx = m + n - 1;
int cur = 0;
while (p >= 0 || q >= 0) {
if (p < 0) {
cur = nums2[q--];
} else if (q < 0) {
cur = nums1[p--];
} else if (nums1[p] < nums2[q]) {
cur = nums2[q--];
} else {
cur = nums1[p--];
}

nums1[idx--] = cur;
}
}
}

Analysis

  • Time Complexity: O(m+n)O(m + n).
  • Space Complexity: O(1)O(1).

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗