Merge Sorted Arrays

Array, Two Pointers

Given two integer arrays nums1 and nums2, sorted in non-decreasing order.

Solutions

Approach - Brute Force Technique

This method also returns a new array that is a sorted merge of the input arrays. However, it does this by first concatenating the two input arrays into one larger array, and then sorting this larger array.

Steps

1. Initialize mergedArray: A new integer array mergedArray is created with a length equal to the sum of the lengths of nums1 and nums2. This array will hold the merged result of nums1 and nums2.

2. Copy nums1 to mergedArray: The elements of nums1 are copied into mergedArray, starting at the beginning of mergedArray.

3. Copy nums2 to mergedArray: The elements of nums2 are copied into mergedArray, starting at the position immediately after the last element of nums1 in mergedArray.

4. Sort mergedArray: The Array.Sort method is called to sort mergedArray in non-decreasing order. This is necessary because the elements of nums1 and nums2 were simply concatenated, not merged in a sorted manner.

5. Return mergedArray: Finally, mergedArray is returned as the result of the method. This array contains all the elements of nums1 and nums2, sorted in non-decreasing order.

public class Solution
{
    public int[] MergeArrays(int[] nums1, int[] nums2)
    {
        int[] mergedArray = new int[nums1.Length + nums2.Length];
        nums1.CopyTo(mergedArray, 0);
        nums2.CopyTo(mergedArray, nums1.Length);
        Array.Sort(mergedArray);
        return mergedArray;
    }

}

Complexity

• Time complexity: O((N+M) log (N+M))

• Space complexity: O(N+M)

The time complexity of the MergeArrays method can be more accurately described as O((N+M) log (N+M)), where N is the size of the first array and M is the size of the second array. This is because the Array.Sort function is called on the merged array, which has a size of N+M, and the time complexity of sorting is O(n log n), where n is the size of the array being sorted. So in this case, n is N+M. Therefore, the time complexity is O((N+M) log (N+M)).

The space complexity of the algorithm is O(N + M). This is because a new array of size N + M is created to store the result. The space used by this array grows linearly with the size of the input arrays, hence the linear space complexity.

Approach - Two Pointers

This method works by maintaining two pointers, one for each input array. The pointers are initially set to the start of their respective arrays. The method then compares the elements at the current pointer positions in both arrays, and the smaller of the two elements is added to the merged array. The pointer for the array from which an element was taken is then incremented. If one of the arrays is exhausted before the other, the remaining elements from the non-exhausted array are copied into the merged array. The method finally returns the merged array. This technique ensures that the merged array is also sorted in non-decreasing order.

Steps

1. Initialization: The function MergeArrays is defined with two parameters, nums1 and nums2, which are the input arrays. It initializes a new array result with a length equal to the sum of the lengths of nums1 and nums2. Three pointers i, j, and k are also initialized to 0. i and j will be used to traverse nums1 and nums2 respectively, and k will be used to insert elements into result.

2. Traverse Both Arrays: The function enters a loop that continues as long as i is less than the length of nums1 and j is less than the length of nums2. This ensures that we only consider elements that are within the bounds of both arrays.

3. Compare and Insert Elements: Inside the loop, the function checks if the current element of nums1 (pointed to by i) is less than the current element of nums2 (pointed to by j). If it is, the element from nums1 is inserted into result at the position pointed to by k, and i and k are incremented. If not, the element from nums2 is inserted into result, and j and k are incremented. This ensures that the smaller of the two current elements is always inserted into result.

4. Store Remaining Elements: After the loop, there may be remaining elements in nums1 or nums2 (but not both). Two additional loops are used to insert any such remaining elements into result. The first loop inserts remaining elements from nums1, and the second loop inserts remaining elements from nums2.

5. Return Result: Finally, the function returns result, which is a sorted array containing all elements from nums1 and nums2.

public int[] MergeArrays(int[] nums1, int[] nums2)
{
    int[] result = new int[nums1.Length + nums2.Length];
    int i = 0, j = 0, k = 0;

    // Traverse both arrays
    while (i < nums1.Length && j < nums2.Length)
    {
        // Check if current element of first array is smaller than current element of second array
        if (nums1[i] < nums2[j])
            result[k++] = nums1[i++];
        else
            result[k++] = nums2[j++];
    }

    // Store remaining elements of first array
    while (i < nums1.Length)
        result[k++] = nums1[i++];

    // Store remaining elements of second array
    while (j < nums2.Length)
        result[k++] = nums2[j++];

    return result;
}

Complexity

• Time complexity: O(N+M)

• Space complexity: O(N+M)

The time complexity of the merge algorithm is O(n + m), where n and m are the lengths of the two input arrays, nums1 and nums2. This is because in the worst case, the algorithm needs to iterate over all elements in both arrays once.

The space complexity of the algorithm is O(n + m). This is because a new array of size n + m is created to store the result. The space used by this array grows linearly with the size of the input arrays, hence the linear space complexity. The rest of the variables used in the algorithm (i, j, and k) use a constant amount of space.