Solution For Merge Sorted Array

The Merge Sorted Array problem on LeetCode asks for a solution to merge two sorted integer arrays into one sorted array. The two input arrays are already sorted in non-descending order, and one of the arrays has enough space at the end to hold all the elements of the two arrays.

Here’s a detailed solution to the problem:

“`
void merge(vector& nums1, int m, vector& nums2, int n) {
int i = m – 1;
int j = n – 1;
int k = m + n – 1;

while (j >= 0) {
    if (i >= 0 && nums1[i] > nums2[j]) {
        nums1[k--] = nums1[i--];
    } else {
        nums1[k--] = nums2[j--];
    }
}

}
“`

Explanation:

We start by initializing three pointers i, j, and k. i and j point to the last elements of nums1 and nums2, respectively. k points to the last position of the merged array, which is m + n – 1.

We then iterate through the arrays in reverse order using a while loop. We compare the values at i and j and use the greater one to fill the kth position in nums1. We decrement k, i, or j based on which value we chose. We continue this process until either we reach the beginning of nums2 (j < 0) or we have filled all positions in nums1 (k < 0).

This algorithm has a time complexity of O(m+n) and a space complexity of O(1), since we are only modifying the existing arrays, and not creating any new data structures.

Step by Step Implementation For Merge Sorted Array

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // two get pointers for nums1 and nums2
        int p1 = 0;
        int p2 = 0;
        // set pointer for nums1
        int p = 0;
       
        // compare elements from nums1 and nums2 
        // and add the smallest one into nums1 
        while ((p1 < m) && (p2 < n)) 
          nums1[p++] = (nums1[p1] < nums2[p2]) ? nums1[p1++] : nums2[p2++];

        // if there are still elements to add
        if (p1 < m) 
            System.arraycopy(nums1, p1, nums1, p, m + n - p1);
        if (p2 < n) 
            System.arraycopy(nums2, p2, nums1, p, m + n - p2);
    }
}

def merge(nums1, m, nums2, n):
    """
    :type nums1: List[int]
    :type m: int
    :type nums2: List[int]
    :type n: int
    :rtype: void Do not return anything, modify nums1 in-place instead.
    """
    
    # two get pointers for nums1 and nums2
    p1 = m - 1
    p2 = n - 1
    
    # set pointer for nums1
    p = m + n - 1
    
    # while there are still elements to compare
    while p1 >= 0 and p2 >= 0:
        if nums1[p1] < nums2[p2]:
            nums1[p] = nums2[p2]
            p2 -= 1
        else:
            nums1[p] = nums1[p1]
            p1 -= 1
        p -= 1
    
    # add missing elements from nums2
    nums1[:p2 + 1] = nums2[:p2 + 1]

function mergeSortedArray(arr1, arr2) {
  // check input
  if (!arr1 || !arr2) {
    return null;
  }

  let mergedArray = [];

  let i = 0;
  let j = 0;

  // compare elements from each array and push the smaller element into the merged array
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      mergedArray.push(arr1[i]);
      i++;
    } else {
      mergedArray.push(arr2[j]);
      j++;
    }
  }

  // if there are elements left in arr1, push them all into the merged array
  while (i < arr1.length) {
    mergedArray.push(arr1[i]);
    i++;
  }

  // if there are elements left in arr2, push them all into the merged array
  while (j < arr2.length) {
    mergedArray.push(arr2[j]);
    j++;
  }

  return mergedArray;
}

vector mergeSortedArray(vector& nums1, vector& nums2) {
    // create an empty vector to store the merged array
    vector mergedArray;
    
    // create two pointer variables to keep track of the current index
    // of each array
    int pointer1 = 0;
    int pointer2 = 0;
    
    // while both pointers are within the bounds of their respective arrays
    while (pointer1 < nums1.size() && pointer2 < nums2.size()) {
        // compare the values at the current indices of each array
        // and push the smaller value into the merged array
        if (nums1[pointer1] <= nums2[pointer2]) {
            mergedArray.push_back(nums1[pointer1]);
            pointer1++;
        }
        else {
            mergedArray.push_back(nums2[pointer2]);
            pointer2++;
        }
    }
    
    // if there are any remaining elements in array 1, append them to the merged array
    while (pointer1 < nums1.size()) {
        mergedArray.push_back(nums1[pointer1]);
        pointer1++;
    }
    
    // if there are any remaining elements in array 2, append them to the merged array
    while (pointer2 < nums2.size()) {
        mergedArray.push_back(nums2[pointer2]);
        pointer2++;
    }
    
    return mergedArray;
}

public class Solution {
    public void Merge(int[] nums1, int m, int[] nums2, int n) {
        // two get pointers for nums1 and nums2
        int p1 = 0;
        int p2 = 0;
        // set pointer for nums1
        int p = 0;
        
        // compare elements from nums1 and nums2 
        // and add the smallest one into nums1 
        while ((p1 < m) && (p2 < n)) 
          nums1[p++] = (nums1[p1] < nums2[p2]) ? nums1[p1++] : nums2[p2++];

        // if there are still elements to add
        if (p1 < m) 
            while (p1 < m) 
                nums1[p++] = nums1[p1++];

        if (p2 < n) 
            while (p2 < n) 
                nums1[p++] = nums2[p2++];
    }
}