LC 0088 [E] Merge Sorted Array - ALawliet/algorithms GitHub Wiki

• combine the lengths and do it backwards to save space
• if one is done early, copy that shorter one over into the longer one

---

guarantees there is enough space in A for B and they are sorted, and empty space is at the end of A, so we merge in reverse

we don't want to make a copy for space: O(m+n), we want in-place constant space: O(1)

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        last = m + n - 1
        
        while m > 0 and n > 0:
            if nums1[m - 1] > nums2[n - 1]:
                nums1[last] = nums1[m - 1]
                m -= 1
            else:
                nums1[last] = nums2[n - 1]
                n -= 1
            last -= 1
            
        while n > 0:
            nums1[last] = nums2[n - 1]
            n -= 1
            last -= 1

class Solution:
    def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        a = m
        b = n
        while a and b:
            end = a + b - 1
            if A[a-1] > B[b-1]:
                A[end] = A[a-1]
                a -= 1
            else:
                A[end] = B[b-1]
                b -= 1

        # if B is larger so B gets exhausted first it is ok and we are done
        # A is large so A gets exhausted first, B remains, so we need to copy remaining B into A
        A[:b] = B[:b]

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        # if the second array is empty, there's nothing to do
        if nums2:
            # pointer for each one of the arrays
            i = j = 0
            # while we don't reach the end of any of the arrays
            while i < m and j < n:
                # if the currect element of nums1 is bigger than the current element of nums2
                if nums1[i] > nums2[j]:
                    # insert the current element of nums2 into nums1 at the current
                    # position of nums1 that we are inspecting
                    nums1.insert(i, nums2[j])
                    # move the nums2 pointer
                    j+=1
                    # the insertion will push all elements beyond the position i to the back
                    # meaning that now the final valid element of of nums1 is at position m+1
                    m+=1
                # and we always move the nums1 pointer because either the current value of nums1 
                # is in the correct position or it was moved one poistion further in the array 
                # to accomodate one value from nums2
                i+=1
            # finally, if we didn't reach the end of nums2
            if j < n:
                # replace all the zeros at the end of nums1 with the rest of the values of nums2 
                # that are not in nums1
                nums1[m:] = nums2[j:]
            else:
                # otherwise, we inserted all `n` elements of nums2 into nums1 and,
                # in this case, we need to delete the last `n` elements of nums1 
                # (they are the zeros that we pushed back to acomodate the nums2 values)
                del nums1[-n:]

public void merge(int[] nums1, int m, int[] nums2, int n) {
    //make a new array to get the answer
    int[] result = new int[m + n];
    //beginning from both head
    int i = 0, j = 0, temp;
    while (i < m || j < n) {
      if (i == m) {
        //if nums1 is ending just copy the nums2
        temp = nums2[j++];
      } else if (j == n) {
        //if nums2 is ending just copy the nums1
        temp = nums1[i++];
      } else if (nums1[i] < nums2[j]) {
        //copy the smaller number
        temp = nums1[i++];
      } else {
        temp = nums2[j++];
      }
      result[i + j - 1] = temp;
    }
    //copy the answer to the nums1
    for (int length = 0; length < n + m; length++) {
      nums1[length] = result[length];
    }
  }