Merge two sorted arrays

Bottom_Up ;) approach

def merge(self, nums1, m, nums2, n):
        while m > 0 and n > 0:
            if nums1[m-1] >= nums2[n-1]:
                nums1[m+n-1] = nums1[m-1]
                m -= 1
            else:
                nums1[m+n-1] = nums2[n-1]
                n -= 1
        if n > 0:
            nums1[:n] = nums2[:n]

Q. Can’t we do it from starting?

Ans. In the two code examples provided, the author starts from the last element of the first array (nums1) and the last element of the second array (nums2) for efficiency reasons. This approach is used to perform an in-place merge of two sorted arrays while avoiding unnecessary element shifting.

Starting from the end of the arrays allows the algorithm to compare the largest elements from both arrays first. Since the arrays are sorted in ascending order, the largest elements are found at the end of each array. By comparing and merging the largest elements first, the algorithm ensures that the elements in the merged array are correctly placed from the end, moving toward the beginning of the array. This approach minimizes the number of shifts or movements required to merge the two arrays and is more efficient than starting from the beginning and potentially shifting elements many times.

Explanation

This is a Python function called “merge” that is used to merge two sorted arrays, “nums1” and “nums2,” into the first array “nums1.” The function takes four parameters: “self” (typically used in a class method, but it seems to be unused in this code), “nums1” (the first sorted array), “m” (the number of valid elements in “nums1”), “nums2” (the second sorted array), and “n” (the number of valid elements in “nums2”).

Here’s how it works:

1. The function starts with a while loop that continues as long as both “m” (elements in “nums1”) and “n” (elements in “nums2”) are greater than 0.

2. Within the loop, it compares the last elements of both arrays (i.e., nums1[m-1] and nums2[n-1]).

3. If the last element of “nums1” is greater than or equal to the last element of “nums2,” it places the larger element in the correct position in “nums1” (nums1[m+n-1]) and decrements “m.”

4. If the last element of “nums2” is greater, it places that element in the same position in “nums1” and decrements “n.”

5. This process continues until one of the arrays (either “nums1” or “nums2”) is completely merged into “nums1,” and “m” or “n” becomes 0.

6. After the while loop, if there are remaining elements in “nums2” (n is greater than 0), it means they are smaller than all the elements in “nums1.” In this case, it copies the remaining elements from “nums2” to the beginning of “nums1.”

The end result is that “nums1” contains a merged and sorted combination of the original elements from both arrays, while taking advantage of the fact that both arrays are sorted to perform the merge efficiently.

Two Pointers Algorithm

• This is again same as previous one, just more variables added.

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

My Approachattempt_before_checking_answer

• The below approach was incorrect, it will need Sorting of one of the array in some condition which will increase thetime_complexity

'''
intuition:
this problem is done well with two heaps, two min heaps should be good here
for the arrays similar approach can be taken, compare first element and put the smaller one in the new array, 
this has to be done in place with num1, is there a left shift in array?
how to do it in place?
the element that will be replaced need to be stored somewhere and there can be multiple element but I will need the smallest one in all the elements.
Can I do it without increasing space complexity, yes can just use and replace elements of second array and maintain the last index in num1 where replacement happened
 
psuedo code:
num1_index = 0
num2_index = 0
while nums1 and nums2: # if one is none return
    if nums1 is none: #edge case
        nums1 = nums2
        return nums1 
        
    if nums2 is none:
        return nums1
        
    if nums1[num1_index] > num2[num2_index]:
        nums1[num1_index], nums2[num2_index] = nums2[num2_index], nums1[num1_index]
        
    
        
    
 
tc: O(n+m)
sc: O(1)
'''
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """