Merge Sorted Array

Easy

Adobe

1 view

Topics:

ArraysTwo Pointers

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
-10⁹ <= nums1[i], nums2[j] <= 10⁹

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

Merge Sorted Array

Easy

Adobe

1 view

Topics:

ArraysTwo Pointers

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
-10⁹ <= nums1[i], nums2[j] <= 10⁹

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the values in `nums1` and `nums2`? Can they be negative, zero, or very large?
If `n` is 0, should `nums1` remain unchanged, or should I clear out the last `m` elements to ensure it's an empty, sorted array (although the description implies leaving `nums1` as is)?
Are duplicate values allowed in both `nums1` and `nums2`, and should the merged array preserve these duplicates?
Is `nums1` guaranteed to have enough allocated space to fit all elements of `nums2` (i.e., `nums1.length >= m + n`)?
Could `m` be 0? If so, should I simply copy all elements from `nums2` to `nums1`?

Brute Force Solution

Approach

The brute force strategy for merging two sorted lists is like combining two decks of playing cards that are already in order. We can simply combine the two decks and then re-sort the entire merged deck to get the final sorted result.

Here's how the algorithm would work step-by-step:

First, put all the elements from both lists into a single, combined list.
Now, rearrange the combined list so that everything is in the correct sorted order, from smallest to largest.

Code Implementation

def merge_sorted_array_brute_force(first_array, first_array_length, second_array, second_array_length):
    # Create a new array to hold all elements
    merged_array = [0] * (first_array_length + second_array_length)
    
    # Copy elements from the first array
    for first_array_index in range(first_array_length):
        merged_array[first_array_index] = first_array[first_array_index]

    # Copy elements from the second array to the end of the merged array
    for second_array_index in range(second_array_length):
        merged_array[first_array_length + second_array_index] = second_array[second_array_index]

    # Sort the merged array.
    # This combines and sorts the data.
    merged_array.sort()

    # Copy the sorted array back into the first array.
    # Required by the problem statement.
    for merged_array_index in range(first_array_length + second_array_length):
        first_array[merged_array_index] = merged_array[merged_array_index]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O((m+n)log(m+n)) – The brute force approach first copies all elements from both arrays into a single array, resulting in m+n elements, where m is the size of nums1 (after considering leading zeros), and n is the size of nums2. The next step involves sorting this combined array. A typical efficient sorting algorithm like merge sort or quicksort would take O(k log k) time where k is the number of elements to be sorted. In this case, k is m+n. Therefore, the overall time complexity of this brute force approach is O((m+n)log(m+n)).

Space Complexity

–

Optimal Solution

Approach

The most efficient way to combine two sorted sequences into one sorted sequence is to work backward. By starting from the end, we avoid the need to constantly shift elements around, which would be slow. This method fills the combined sequence from the end to the beginning, ensuring everything stays in order.

Here's how the algorithm would work step-by-step:

Begin at the very end of the space where the final, merged sequence will live.
Compare the last elements of both input sequences.
Take the larger of the two elements and put it in the final spot of the merged sequence.
Move to the next available spot towards the beginning of the merged sequence, and move to the next element toward the start of whichever sequence you used to pick the larger element.
Keep comparing and moving backward until one of the input sequences runs out of elements.
If there are any elements left in the other sequence, just copy them over to the beginning of the merged sequence, because they are already in the correct order.
The combined sequence is now fully sorted, without needing to move any element already placed.

Code Implementation

def merge_sorted_array(nums1, nums1_length, nums2, nums2_length):
    merged_array_length = nums1_length + nums2_length
    
    # Initialize pointers to the end of each array.
    first_array_pointer = nums1_length - 1
    second_array_pointer = nums2_length - 1
    merged_array_pointer = merged_array_length - 1

    # Merge from the end until one array is exhausted.
    while first_array_pointer >= 0 and second_array_pointer >= 0:
        # Pick the larger element and place it at the end.
        if nums1[first_array_pointer] > nums2[second_array_pointer]:
            nums1[merged_array_pointer] = nums1[first_array_pointer]
            first_array_pointer -= 1
        else:
            nums1[merged_array_pointer] = nums2[second_array_pointer]
            second_array_pointer -= 1
        merged_array_pointer -= 1

    # Copy any remaining elements from nums2 to nums1.
    # These are already in sorted order.
    while second_array_pointer >= 0:
        nums1[merged_array_pointer] = nums2[second_array_pointer]
        second_array_pointer -= 1
        merged_array_pointer -= 1

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m + n) – The algorithm iterates through the elements of both input arrays, nums1 (of effective length m) and nums2 (of length n), exactly once. The while loop continues as long as there are elements in either of the arrays to be considered. In the worst case, it checks all m elements of nums1 and all n elements of nums2 before completing, placing them into the merged array. Thus, the total number of operations is proportional to m + n, which simplifies to O(m + n).

Space Complexity

O(1) – The algorithm operates in-place, modifying the first array directly. It uses only a few integer variables to keep track of the current positions in the arrays being merged. The number of variables does not depend on the size of the input arrays. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
nums1 is empty (m=0), nums2 has elements (n>0)	Simply copy all elements from nums2 to nums1.
nums2 is empty (n=0), nums1 has elements (m>0)	nums1 is already sorted, no action required.
Both arrays are empty (m=0, n=0)	No operation needed; nums1 remains empty.
All elements in nums2 are smaller than all elements in nums1	The solution should correctly place all elements of nums2 at the beginning of nums1.
All elements in nums2 are larger than all elements in nums1	The solution should correctly place all elements of nums2 at the end of nums1.
nums1 and nums2 contain duplicate values	The merging process should handle duplicates correctly, maintaining the sorted order.
nums1 contains very large or very small numbers	The comparison logic should work correctly even with extreme integer values (avoiding overflow during comparison if possible, relying on language's int comparison behavior).
m + n equals the maximum array size representable by the programming language	Ensure no out-of-bounds write occurs when merging elements near the array boundary (check index bounds before accessing).