leetcode-study

88. Merge Sorted Array

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Merges two sorted arrays (nums1 and nums2) into one sorted array in-place.
        
        Parameters:
            nums1 (List[int]): The first sorted array, which has a length of m + n. 
                               The first m elements are valid, followed by n zeros to provide extra space.
            m (int): Number of valid elements in nums1.
            nums2 (List[int]): The second sorted array containing n valid elements.
            n (int): Number of elements in nums2.
            
        Operation:
            The function modifies nums1 in-place, merging it with nums2 such that the final array is sorted 
            in non-decreasing order. The merging is done from the end to the beginning of nums1 to avoid overwriting
            unprocessed elements.
        
        Returns:
            None: The result is directly stored in nums1.
        """
        # Set pointers for nums1, nums2, and the merge position in nums1
        i = m - 1         # Pointer for the last valid element in nums1
        j = n - 1         # Pointer for the last element in nums2
        k = m + n - 1     # Pointer for the last position in nums1 (where merge happens)

        # Merge in reverse order: compare elements from the back and place the larger one at the k-th position.
        while j >= 0:  # We only need to check nums2 since nums1's remaining items are already in place if nums2 is exhausted.
            # Check if there are still elements in nums1 and if the current element in nums1 is larger than that in nums2.
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1  # Move the pointer in nums1 to the left.
            else:
                nums1[k] = nums2[j]
                j -= 1  # Move the pointer in nums2 to the left.
            k -= 1  # Move the merge pointer to the left for the next placement.

---

Summary of Techniques and Approaches:

• Two-Pointer Technique (From the End):
  • Technique: Use two pointers starting at the end of each sorted subarray.
  • Application: This is useful when merging or comparing elements from two arrays without additional memory allocation.
  • Tip: When dealing with sorted arrays and you need to merge them in-place, iterating from the end avoids overwriting unmerged values.
• In-Place Modification:
  • Technique: Modify the array directly using available space.
  • Application: When constraints require O(1) extra space; important for space optimization.
  • Tip: Identify opportunities where extra space is pre-allocated and utilize it effectively to minimize space complexity.
• Iterative Comparison and Conditional Assignment:
  • Technique: Compare current elements and conditionally assign values to build the final array.
  • Application: Common in scenarios where you have two or more sorted sequences and need to maintain overall order.
  • Tip: Leverage conditional logic to ensure correct ordering while minimizing time complexity.
• Time Complexity Optimization (O(m + n)):
  • Approach: Process each element exactly once.
  • Application: Anytime you need to traverse through two datasets of known sizes without nested iteration.
  • Tip: Recognize sorted data properties and use them to reduce redundant comparisons or iterations.

These techniques are broadly applicable to many problems involving merging sorted data, in-place operations, and efficient array manipulation.