Merge Two Sorted Arrays

Easy

Given two sorted integer arrays nums1 and nums2, merge them into a single sorted array. Assume nums1 has enough space at the end to hold all elements.

Examples

InputOutput
nums1 = [1,2,3,0,0,0], m=3, nums2 = [2,5,6], n=3[1,2,2,3,5,6]

Python Solution

def merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
    p1, p2, p = m - 1, n - 1, m + n - 1
    while p1 >= 0 and p2 >= 0:
        if nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1
    nums1[:p2 + 1] = nums2[:p2 + 1]

JavaScript Solution

function merge(nums1, m, nums2, n) {
  let p1 = m - 1, p2 = n - 1, p = m + n - 1;
  while (p1 >= 0 && p2 >= 0) {
    nums1[p--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
  }
  while (p2 >= 0) nums1[p--] = nums2[p2--];
}

Step-by-Step Explanation

  1. Use three pointers: start from the end of both arrays and the end of the output.
  2. Compare elements and place the larger one at position p.
  3. Decrement the pointer of the array we took from.
  4. If nums2 has remaining elements, copy them over.

Complexity Analysis

TimeO(m + n)
SpaceO(1)

Tags

ArrayTwo Pointers

Related Problems

Binary SearchRemove Duplicates from Sorted Array

Related Tools

JSON Formatter

All Problems

Two SumReverse a StringPalindrome CheckFizzBuzzBinary SearchReverse Linked ListValid ParenthesesMaximum Subarray (Kadane's Algorithm)Remove Duplicates from Sorted ArrayNth Fibonacci NumberValid AnagramFirst Unique CharacterClimbing StairsRoman to IntegerBest Time to Buy and Sell StockContains DuplicateMove ZeroesIntersection of Two ArraysLongest Common Prefix