Merge Sorted Array

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.

Problem Statement

The problem is to merge two given integer arrays nums1 and nums2, which are sorted in non-decreasing order, into a single array. The merged array should also be sorted in non-decreasing order and should be stored in nums1 array.

The length of nums1 array is m+n, where m denotes the number of elements in nums1, and n denotes the number of elements in nums2. The first m elements of nums1 should contain the merged sorted array, and the remaining n elements of nums1 should be set to 0 and ignored.

The solution should not return the final sorted array, but instead, modify the nums1 array in-place.

Examples

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.

Clarifying Questions

1. Are the arrays nums1 and nums2 guaranteed to be of equal length?
2. Can we assume that the non-zero elements in nums1 are already sorted in non-decreasing order?
3. Can we assume that the non-zero elements in nums2 are already sorted in non-decreasing order?
4. Is it allowed to use additional data structures or do we need to perform the merge in-place?
5. Do we need to consider edge cases such as empty arrays or arrays with only zero elements?

Solutions

There are several approaches that can be used to solve this problem:

1. Brute Force

2. Two-pointers

3. Merge and Sort

4. Merge and Insert

5. In-Place Merging

All of the above approaches can be used to solve this problem, but the best approach would depend on various factors like input size, time complexity, and space complexity requirements.

Brute Force:

Iterate over both arrays, compare the elements at each index, and insert the smaller element into a new array until both arrays are exhausted. Then, copy the new array back into nums1.

Algorithm:

1. Initialize an empty array merged.
2. Initialize two pointers, i and j, to point to the first element of nums1 and nums2, respectively.
3. While both arrays have elements:
   • If nums1[i] is smaller than or equal to nums2[j], append nums1[i] to merged and increment i.
   • Otherwise, append nums2[j] to merged and increment j.
4. If nums1 still has elements, append the remaining elements to merged.
5. If nums2 still has elements, append the remaining elements to merged.
6. Copy the elements from merged back into nums1.

      
     
      public void Merge(int[] nums1, int m, int[] nums2, int n) {
          int[] merged = new int[m + n];
          int i = 0, j = 0, k = 0;
          
          while (i < m && j < n) {
              if (nums1[i] <= nums2[j]) {
                  merged[k++] = nums1[i++];
              } else {
                  merged[k++] = nums2[j++];
              }
          }
          
          while (i < m) {
              merged[k++] = nums1[i++];
          }
          
          while (j < n) {
              merged[k++] = nums2[j++];
          }
          
          Array.Copy(merged, nums1, m + n);
      }
      
      
        
      
    

      
     
        def merge(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
            merged = []
            i = j = k = 0
            
            while i < m and j < n:
                if nums1[i] <= nums2[j]:
                    merged.append(nums1[i])
                    i += 1
                else:
                    merged.append(nums2[j])
                    j += 1
                    
            while i < m:
                merged.append(nums1[i])
                i += 1
                
            while j < n:
                merged.append(nums2[j])
                j += 1
                
            nums1[:m+n] = merged
    
    
      
    

      
     
      public void merge(int[] nums1, int m, int[] nums2, int n) {
          int[] merged = new int[m + n];
          int i = 0, j = 0, k = 0;
          
          while (i < m && j < n) {
              if (nums1[i] <= nums2[j]) {
                  merged[k++] = nums1[i++];
              } else {
                  merged[k++] = nums2[j++];
              }
          }
          
          while (i < m) {
              merged[k++] = nums1[i++];
          }
          
          while (j < n) {
              merged[k++] = nums2[j++];
          }
          
          System.arraycopy(merged, 0, nums1, 0, m + n);
      }
      
      
      
    

      
   
      void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> merged(m + n);
        int i = 0, j = 0, k = 0;
        
        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }
        
        while (i < m) {
            merged[k++] = nums1[i++];
        }
        
        while (j < n) {
            merged[k++] = nums2[j++];
        }
        
        nums1 = merged;
    }
    
      
    

Time complexity: O((m+n)^2)

Space complexity: O(m+n)

This approach involves creating a new array and iterating over both input arrays to add elements to the new array, while keeping it sorted. For each element in the second array, we compare it with each element in the first array and insert it in the correct position. The time complexity of this approach is O((m+n)^2), because for each element in the second array we have to compare it to all the elements in the first array. The space complexity is O(m+n), because we create a new array to store the merged elements. This approach is not efficient and is not practical for large inputs, but it is simple to implement.

Two-pointers:

Initialize two pointers, one for each array, and iterate over both arrays, comparing the elements at each pointer's current position. The smaller element is inserted into nums1, and the corresponding pointer is moved one position to the right. This process continues until one of the arrays is exhausted. Then, copy the remaining elements from the non-exhausted array into nums1.

Algorithm:

1. Initialize two pointers, i and j, to point to the first element of nums1 and nums2, respectively.
2. While both arrays have elements:
   • If nums1[i] is smaller than or equal to nums2[j], increment i.
   • Otherwise, shift the elements in nums1 from index i to m+j one position to the right and insert nums2[j] at index i. Increment i and j.
3. If nums2 still has elements, copy the remaining elements to nums1.

      
     
        public void Merge(int[] nums1, int m, int[] nums2, int n) {
          // Initialize three pointers: i for nums1, j for nums2, and k for the end of nums1
          int i = m - 1, j = n - 1, k = m + n - 1;
          
          // While both arrays have elements, compare the current elements from nums1 and nums2 and insert the larger one at the end of nums1
          while (i >= 0 && j >= 0) {
              if (nums1[i] >= nums2[j]) {
                  nums1[k--] = nums1[i--]; // Insert the current element of nums1 and decrement i and k
              } else {           
                 nums1[k--] = nums2[j--]; // Insert the current element of nums2 and decrement j and k
              }
          }
          
          // If there are any remaining elements in nums2, insert them at the end of nums1
          while (j >= 0) {
              nums1[k--] = nums2[j--];
          }
      }
      
      
      
    

      
     
        def merge(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
            i, j, k = m - 1, n - 1, m + n - 1
            
            while i >= 0 and j >= 0:
                if nums1[i] >= nums2[j]:
                    nums1[k] = nums1[i]
                    i -= 1
                else:
                    nums1[k] = nums2[j]
                    j -= 1
                k -= 1
                
            while j >= 0:
                nums1[k] = nums2[j]
                j -= 1
                k -= 1
    
    
      
    

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

      
 
  
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    
    while (i >= 0 && j >= 0) {
        if (nums1[i] >= nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
    
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}

      
    

Time complexity: O(m+n)

Space complexity: O(1)

This approach involves traversing the two arrays using two pointers until all the elements have been merged. It is a linear-time algorithm and has a space complexity of O(1) because it does not use any additional data structures.

Merge and Sort:

Merge the two arrays into a new array, then sort the new array, and copy the sorted elements back into nums1.

Algorithm:

1. Merge the two arrays into a new array, merged.
2. Sort the merged array.
3. Copy the elements from merged back into nums1.

      
        public void Merge(int[] nums1, int m, int[] nums2, int n) {
          // Copy the elements of nums2 into the end of nums1
          Array.Copy(nums2, 0, nums1, m, n);
          // Sort the merged array in non-decreasing order
          Array.Sort(nums1);
      }
      
        
      
    

      
        def merge(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
            # Copy the elements of nums2 into the end of nums1
            nums1[m:] = nums2
            # Sort the merged array in non-decreasing order
            nums1.sort()
    
      
    

      
      public void merge(int[] nums1, int m, int[] nums2, int n) {
          // Copy the elements of nums2 into the end of nums1
          System.arraycopy(nums2, 0, nums1, m, n);
          // Sort the merged array in non-decreasing order
          Arrays.sort(nums1);
      }
      
      
    

      
  
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // Copy the elements of nums2 into the end of nums1
        copy(nums2.begin(), nums2.end(), nums1.begin() + m);
        // Sort the merged array in non-decreasing order
        sort(nums1.begin(), nums1.end());
    }
    
      
    

Time complexity: O((m+n)log(m+n))

Space complexity: O(m+n)

This approach involves merging the two arrays and then sorting the resulting array. The time complexity is dominated by the sorting algorithm used, which is usually O((m+n)log(m+n)). The space complexity is O(m+n) because a new array is created to store the merged and sorted elements.

In-Place Merging:

Starting from the end of nums1, compare the last elements of both arrays and insert the larger element at the end of nums1. Move the pointer of the array that contains the larger element to the left and repeat until one of the arrays is exhausted. Then, copy the remaining elements from the non-exhausted array into nums1.

Algorithm:

1. Initialize two pointers, i and j, to point to the last non-zero element of nums1 and nums2, respectively.
2. Initialize a pointer, k, to point to the last element of nums1.
3. While both i and j are non-negative:
   • If nums1[i] is greater than nums2[j], copy nums1[i] to nums1[k] and decrement i. Otherwise, copy nums2[j] to nums1[k] and decrement j.
   • Decrement k.
4. If j is still non-negative, copy the remaining elements from nums2 to nums1.

      
     
      public void Merge(int[] nums1, int m, int[] nums2, int n) {
          int i = m - 1; // Index of last element in nums1
          int j = n - 1; // Index of last element in nums2
          int k = m + n - 1; // Index of last element in merged array
      
          // Merge nums1 and nums2 into a single sorted array
          while (j >= 0) {
              if (i >= 0 && nums1[i] > nums2[j]) {
                  nums1[k--] = nums1[i--];
              } else {
                  nums1[k--] = nums2[j--];
              }
          }
      }
      
        
      
    

      
     
        def merge(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
            i = m - 1 # Index of last element in nums1
            j = n - 1 # Index of last element in nums2
            k = m + n - 1 # Index of last element in merged array
        
            # Merge nums1 and nums2 into a single sorted array
            while j >= 0:
                if i >= 0 and nums1[i] > nums2[j]:
                    nums1[k] = nums1[i]
                    i -= 1
                else:
                    nums1[k] = nums2[j]
                    j -= 1
                k -= 1
    
      
    

      
     
      public void merge(int[] nums1, int m, int[] nums2, int n) {
          int i = m - 1; // Index of last element in nums1
          int j = n - 1; // Index of last element in nums2
          int k = m + n - 1; // Index of last element in merged array
      
          // Merge nums1 and nums2 into a single sorted array
          while (j >= 0) {
              if (i >= 0 && nums1[i] > nums2[j]) {
                  nums1[k--] = nums1[i--];
              } else {
                  nums1[k--] = nums2[j--];
              }
          }
      }
      
      
      
    

      
     
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1; // Index of last element in nums1
        int j = n - 1; // Index of last element in nums2
        int k = m + n - 1; // Index of last element in merged array
    
        // Merge nums1 and nums2 into a single sorted array
        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
    }
    
      
    

Time complexity: O(m+n)

Space complexity: O(1)

This approach involves merging the two arrays in-place, by starting from the end of both arrays and inserting the largest element into the end of the first array. The time complexity is O(m+n) because each element is compared and inserted once. The space complexity is O(1) because no additional data structures are used.