Leetcode 88- Merge Sorted Array | Two Pointer

Merging sorted arrays is a fundamental problem in computer science. The task is to combine two sorted arrays into one sorted array, maintaining the order. The Merge Sorted Array presents this classic problem with a twist — you are asked to merge the arrays in-place. This means that instead of using extra space, you must merge the second array into the first array directly.

In this article, we will explore two methods to solve this problem: a brute force approach and an efficient Two-Pointer approach. We’ll also go through the Java code for both solutions and explain each step in simple language.

Problem Description:

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

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]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

Problem Link :Merge Sorted Array – LeetCode

Solutions:

Approach 1: Brute Force Solution

The brute force approach is the simplest method to solve the problem, but it is not the most efficient. In this method, we can create a new array to hold the elements from both nums1 and nums2. Once the elements are copied, we sort the new array and copy the sorted values back into nums1.

Steps:

• Create a new array to store the merged result.
• Copy all elements from nums1 and nums2 into this new array.
• Sort the new array.
• Copy the sorted elements back into nums1.

Java Code:

import java.util.Arrays;

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Create a new array to store merged elements
        int[] merged = new int[m + n];

        // Copy elements from nums1
        for (int i = 0; i < m; i++) {
            merged[i] = nums1[i];
        }

        // Copy elements from nums2
        for (int j = 0; j < n; j++) {
            merged[m + j] = nums2[j];
        }

        // Sort the merged array
        Arrays.sort(merged);

        // Copy back the sorted array to nums1
        for (int i = 0; i < merged.length; i++) {
            nums1[i] = merged[i];
        }
    }
}

Explanation:

• We first create a new array merged of size m + n to hold all the elements of both arrays.
• We copy the valid elements of nums1 (i.e., the first m elements) into merged.
• Then, we copy the n elements of nums2 into the merged array.
• We use Arrays.sort() to sort the merged array.
• Finally, we copy the sorted elements back into nums1.

Time and Space Complexity:

• Time Complexity: O((m + n) log (m + n)) — Sorting dominates the time complexity.
• Space Complexity: O(m + n) — We are using extra space to store the merged array.

Although this method works, it’s not efficient due to the extra space required and the sorting step, which increases time complexity.

Approach 2: Efficient Two-Pointer Solution

The brute force method works, but it is not space-efficient. We can solve this problem using a more optimized method: the Two-Pointer Approach. This method allows us to merge the arrays in O(n) time without using extra space.

The idea is simple: since both arrays are already sorted, we can use two pointers to track the largest elements and merge from the end of nums1. We compare the elements from the back of both arrays and place the larger one in the correct position in nums1.

Steps:

1.Initialize three pointers:

• p1 for the last valid element of nums1 (i.e., m - 1).
• p2 for the last element of nums2 (i.e., n - 1).
• p for the last position of nums1 (i.e., m + n - 1).

2.Compare elements from the end of nums1 and nums2, and place the larger element at the back of nums1.

3.Move pointers accordingly and continue this process until all elements are merged.

Java Code:

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Pointers for nums1, nums2, and the end of nums1
        int p1 = m - 1;
        int p2 = n - 1;
        int p = m + n - 1;

        // Merge the arrays in reverse order
        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] > nums2[p2]) {
                nums1[p] = nums1[p1];
                p1--;
            } else {
                nums1[p] = nums2[p2];
                p2--;
            }
            p--;
        }

        // If there are remaining elements in nums2, copy them over
        while (p2 >= 0) {
            nums1[p] = nums2[p2];
            p--;
            p2--;
        }
    }
}

Complexity:

• Time-Complexity: O(m+n) because we traverse each element in nums1 and nums2 only once.
• Space-Complexity: O(1) since we are merging the arrays in-place without using extra space.

Explanation:

• We start comparing elements from the back because the space at the end of nums1 is unused. This ensures that we don’t overwrite elements we haven’t processed yet.
• The while loop compares the elements of nums1 and nums2 and fills nums1 from the back, ensuring that it remains sorted.
• If there are remaining elements in nums2 after finishing the comparison, we copy them into nums1.

This is the most efficient solution with a linear time complexity, making it optimal for larger datasets.

Comparison of Approaches

Conclusion

The Two-Pointer Technique is the best approach for solving merge sorted array problem, as it merges the two sorted arrays in linear time and without using extra space. The Brute Force approach, while easier to understand, is less efficient and impractical for larger datasets.