Merge Sorted Array

🏠 ⬅️ ➡️

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] Explanation: The arrays we are merging are [1,2,3] and [2,5,6]. The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1] Explanation: The arrays we are merging are [1] and []. The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1 Output: [1] Explanation: The arrays we are merging are [] and [1]. The result of the merge is [1]. Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints:

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -109 <= nums1[i], nums2[j] <= 109

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: m = 3, n = 3
    integer, dimension(m+n) :: nums1 = [1,2,3,0,0,0]
    integer, dimension(n) :: nums2 = [2,5,6]

    call merge_sorted_arrays(nums1, m, nums2, n)

    write (*, '(A)') 'nums1 = ', nums1

contains

subroutine merge_sorted_arrays(nums1, m, nums2, n)
    implicit none
    integer, intent(inout) :: nums1(:)
    integer, intent(in) :: m, n
    integer, intent(in) :: nums2(:)
    integer :: i, j, k

    ! Merge nums1 and nums2 into a single array sorted in non-decreasing order
    ! Store the final sorted array inside nums1
    ! nums1 has a length of m + n, where the first m elements denote the elements that should be merged
    ! and the last n elements are set to 0 and should be ignored
    ! nums2 has a length of n

    i = 1
    j = 1
    k = 1

    do while (i <= m .and. j <= n)
        if (nums1(i) < nums2(j)) then
            nums1(k) = nums1(i)
            i = i + 1
        else
            nums1(k) = nums2(j)
            j = j + 1
        end if
        k = k + 1
    end do

    if (i > m) then
        nums1(k:) = nums2(j:)
    end if
end subroutine merge_sorted_arrays

end program main
❌ Compiled
❌ Executed
❌ Correct 
module merge_sorted_arrays

implicit none

contains

subroutine merge_sorted_arrays(nums1, m, nums2, n)

integer, intent(inout) :: nums1(m + n)
integer, intent(in) :: m, n
integer :: i, j, k

! Initialize pointers
i = 1
j = 1
k = 1

! Loop through both arrays and merge them
do while (i <= m .and. j <= n)
    if (nums1(i) <= nums2(j)) then
        nums1(k) = nums1(i)
        i = i + 1
    else
        nums1(k) = nums2(j)
        j = j + 1
    end if
    k = k + 1
end do

! Copy the remaining elements from nums1
if (i <= m) then
    nums1(k:m + n) = nums1(i:m + n)
end if

! Copy the remaining elements from nums2
if (j <= n) then
    nums1(k:m + n) = nums2(j:n)
end if

end subroutine merge_sorted_arrays

end module merge_sorted_arrays

program test

use merge_sorted_arrays

implicit none

integer, parameter :: m = 3, n = 3
integer :: nums1(m + n)
integer :: nums2(n)

! Test case 1
nums1 = [1, 2, 3, 0, 0, 0]
nums2 = [2, 5, 6]
call merge_sorted_arrays(nums1, m, nums2, n)
write (*,*) nums1

! Test case 2
nums1 = [1]
nums2 = []
call merge_sorted_arrays(nums1, m, nums2, n)
write (*,*) nums1

! Test case 3
nums1 = [0]
nums2 = [1]
call merge_sorted_arrays(nums1, m, nums2, n)
write (*,*) nums1

end program test
🌐 Data from online sources 
def merge(nums1, m, nums2, n):
    i, j, k = m - 1, n - 1, m + n - 1
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    while j >= 0:
        nums1[k] = nums2[j]
        k -= 1
        j -= 1

We use a two-pointer approach to merge nums1 and nums2 in reverse order. Initialize three pointers i, j, and k pointing to the last elements of nums1, nums2, and the merged nums1 array respectively.

Iterate in a while loop until i and j are both less than 0. Compare the values of nums1[i] and nums2[j]. If nums1[i] is greater, assign nums1[i] at position k in nums1, decrement i and k. Otherwise, assign nums2[j] at position k in nums1, and decrement j and k. This process continues for all elements in nums2.

After the loop, if there are still elements remaining in nums2 (j >= 0), copy the remaining elements of nums2 to nums1. In this way, we merge nums1 and nums2 in non-decreasing order.

🌐 Data from online sources 
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j])
            nums1[k--] = nums1[i--];
        else
            nums1[k--] = nums2[j--];
    }
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}

We use a two-pointer approach to merge nums1 and nums2 in reverse order. Initialize three pointers i, j, and k pointing to the last elements of nums1, nums2, and the merged nums1 array respectively.

Iterate in a while loop until i and j are both less than 0. Compare the values of nums1[i] and nums2[j]. If nums1[i] is greater, assign nums1[i] at position k in nums1, decrement i and k. Otherwise, assign nums2[j] at position k in nums1, and decrement j and k. This process continues for all elements in nums2.

After the loop, if there are still elements remaining in nums2 (j >= 0), copy the remaining elements of nums2 to nums1. In this way, we merge nums1 and nums2 in non-decreasing order.