Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0088 - Merge Sorted Array
    0088 - Merge Sorted Array
    0088 - Merge Sorted Array
    0088 - Merge Sorted Array

    0088 - Merge Sorted Array

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/merge-sorted-array/

    Solution 1 - Three Pointer (End to Start)

    Merge in-place by filling nums1 from the end. Use three pointers: i at the last valid element of nums1, j at the last element of nums2, and k at the last position of nums1. Compare elements from the end of both arrays and place the larger one at position k, moving backwards.

    TimeComplexity:O(m+n)TimeComplexity: O(m + n)TimeComplexity:O(m+n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    Solution 2 - Sort After Copy

    Copy all elements of nums2 into the trailing zeros of nums1, then sort the entire array. This is simpler but less optimal due to the sorting step.

    TimeComplexity:O((m+n)log⁡(m+n))TimeComplexity: O((m+n) \log(m+n))TimeComplexity:O((m+n)log(m+n))
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)
    """ 0088.1 - Merge Sorted Array - Solution 1 - Three Pointer (End to Start) """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """Merge Sorted Array Function (modifies nums1 in-place)"""
        i = m - 1      # pointer for nums1's valid elements
        j = n - 1      # pointer for nums2
        k = m + n - 1  # pointer for the merge position in nums1

        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


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    nums1 = [1, 2, 3, 0, 0, 0]
    Solution().merge(nums1, 3, [2, 5, 6], 3)
    print(nums1)  # [1, 2, 2, 3, 5, 6]

    nums1 = [1]
    Solution().merge(nums1, 1, [], 0)
    print(nums1)  # [1]

    nums1 = [0]
    Solution().merge(nums1, 0, [1], 1)
    print(nums1)  # [1]


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0088.2 - Merge Sorted Array - Solution 2 - Sort After Copy """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """Merge Sorted Array Function (modifies nums1 in-place)"""
        for j in range(n):
            nums1[m + j] = nums2[j]
        nums1.sort()


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    nums1 = [1, 2, 3, 0, 0, 0]
    Solution().merge(nums1, 3, [2, 5, 6], 3)
    print(nums1)  # [1, 2, 2, 3, 5, 6]

    nums1 = [1]
    Solution().merge(nums1, 1, [], 0)
    print(nums1)  # [1]

    nums1 = [0]
    Solution().merge(nums1, 0, [1], 1)
    print(nums1)  # [1]


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()