We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Merge Sorted Array

Number: 88

Difficulty: Easy

Paid? No

Companies: Meta, Google, Amazon, Microsoft, Bloomberg, Hubspot, Apple, Yandex, HCL, Accenture, Avito, TikTok, LinkedIn, EPAM Systems, Oracle, Infosys, tcs, Agoda, Swiggy, Adobe, Yahoo, Uber, PayPal, IBM, Squarespace, Cisco, Intuit, Goldman Sachs, Walmart Labs, Shopee, Atlassian, Nvidia, Rakuten, Tinkoff, Palo Alto Networks, Criteo

Problem Description

Given two sorted arrays nums1 and nums2, where nums1 has enough space to hold all elements of nums2, merge nums2 into nums1 so that nums1 becomes a single sorted array.

Key Insights

  • Both arrays are already sorted in non-decreasing order.
  • The merge should be done in-place into nums1.
  • Start merging from the end to avoid overwriting elements in nums1.
  • Use two pointers, one for nums1 and one for nums2, and a tail pointer for placement.

Space and Time Complexity

Time Complexity: O(m + n)
Space Complexity: O(1)

Solution

We use a two-pointer approach starting from the end of both arrays. Initialize three pointers:

  • p1 pointing to the last valid element in nums1.
  • p2 pointing to the last element in nums2.
  • tail pointing to the last index of nums1.

While both pointers are valid, compare the elements pointed by p1 and p2, placing the larger element at the tail position. Decrement the corresponding pointer and the tail pointer. Finally, if any elements remain in nums2 (i.e., p2 >= 0), copy them over into nums1. This solution leverages the extra space at the end of nums1 and ensures the merge is done in-place in linear time.

Code Solutions

def merge(nums1, m, nums2, n):
    # Initialize pointers for nums1, nums2 and the tail index
    p1 = m - 1
    p2 = n - 1
    tail = m + n - 1

    # Merge arrays from the end by choosing the larger element
    while p1 >= 0 and p2 >= 0:
        if nums1[p1] > nums2[p2]:
            nums1[tail] = nums1[p1]
            p1 -= 1  # Move pointer in nums1
        else:
            nums1[tail] = nums2[p2]
            p2 -= 1  # Move pointer in nums2
        tail -= 1  # Move tail pointer

    # Copy any remaining elements from nums2 into nums1
    while p2 >= 0:
        nums1[tail] = nums2[p2]
        p2 -= 1
        tail -= 1
← Back to All Questions