[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 ${\mathit{\text{nums}}}_2$ into the rear of array ${\mathit{\text{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))$ .
• Space Complexity: $O(log(m+n))$ .

Two Pointers

Since two arrays ${\mathit{\text{nums}}}_1$ and ${\mathit{\text{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)$.
• Space Complexity: $O(m+n)$.

Reverse Two Pointers

Since the extra space of ${\mathit{\text{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 $len1$ and $len2$ to point to the tails of $nums1$ and $nums2$, traversal from the tail and compare the values, and set the pointer $len$ to point to the end of ${\mathit{\text{nums}}}_1$. After each traversal of the size of the comparison value, it will be filled.

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

The process is show as the following images.

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)$.
• Space Complexity: $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. 😉😃💗