88. Merge Sorted Array


Problem Description

You have two sorted arrays nums1 and nums2 with lengths m and n, respectively. These arrays are sorted in non-decreasing order, which means each element is equal to or greater than the previous element. Initially, the array nums1 has m elements in it, and an additional n spaces filled with 0 to allow space for merging. The array nums2 has exactly n elements.

The goal is to merge these two arrays so that the nums1 array becomes a single sorted array in non-decreasing order. The merge should happen in-place in the nums1 array, using the additional space provided so that it can fit all m + n elements by the end.

Intuition

The challenge is to merge the two sorted arrays in-place, without using extra space for another array. Our intuition might suggest starting from the beginning of both arrays and comparing the elements one by one. However, this approach would require shifting elements in nums1 to make space for elements from nums2, which is not efficient.

To efficiently merge these arrays, we leverage the fact that we have empty space at the end of nums1 where n zeros are placed. This allows us to fill nums1 from the end (right to left), placing the largest elements first and avoiding the need for shifting.

We use a two-pointer approach. The first pointer i starts at the last actual element in nums1, and the second pointer j starts at the last element in nums2. We also have a third pointer k that starts at the very end of nums1, and it indicates where the next element should be placed.

Each step involves comparing the elements pointed by i and j. The larger of the two elements is placed at the position indicated by k, and then we move the respective pointer (i or j) and k one step back. We repeat this process until all elements from nums2 are placed into nums1. If nums1 still has elements left when nums2 runs out, they are already in place as the array is sorted. If nums2 had the greatest element, it would be placed last, ensuring the non-decreasing order is maintained throughout the process.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The implementation of the solution starts with the recognition that by merging the arrays from right to left, you can avoid additional space complexities and time-consuming operations like shifting elements.

The pointers i, j, and k are initialized as follows: i starts at m - 1, j at n - 1, and k at m + n - 1.

The algorithm is inherently a comparison between the elements pointed to by i and j. Let's walk through the steps:

  • Compare the elements at pointer i in nums1 and at pointer j in nums2.
  • If nums1[i] is greater, place nums1[i] in nums1[k], and decrement both i and k.
  • If nums2[j] is greater or i is out of bounds (which means all elements of nums1 have been placed), place nums2[j] in nums1[k], and decrement both j and k.

This logic is concisely written in a loop that continues until all elements of nums2 are processed, which is when j < 0. The condition i >= 0 and nums1[i] > nums2[j] ensures that you are still within bounds of nums1 and that the current element in nums1 is indeed larger than nums2[j].

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

This approach does not require any extra data structures. It utilizes the space already allocated within nums1 and takes advantage of the sorted order, allowing an efficient in-place merge. The pattern used here is commonly known as the two-pointer technique, which is often applied to problems that involve sorted arrays.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach.

Assume our nums1 array is [1, 2, 3, 0, 0, 0] with m = 3, and our nums2 array is [2, 5, 6] with n = 3. The goal is to merge nums2 into nums1 so that it becomes a single sorted array.

Following the steps described in the solution approach:

  1. Set i to m - 1, which is 2, pointing at the last actual element in nums1.
  2. Set j to n - 1, which is 2, pointing at the last element in nums2.
  3. Set k to m + n - 1, which is 5, pointing to the last space in nums1.

Now we begin comparing and placing elements:

  • First iteration:

    • Compare nums1[i] (which is 3) and nums2[j] (which is 6).
    • Since nums2[j] is greater, we place 6 in nums1[k].
    • Decrement j to 1 and k to 4.
    • Now, nums1 looks like [1, 2, 3, 0, 0, 6].
  • Second iteration:

    • Compare nums1[i] (which is 3) and nums2[j] (which is 5).
    • Since nums2[j] is greater, we place 5 in nums1[k].
    • Decrement j to 0 and k to 3.
    • Now, nums1 looks like [1, 2, 3, 0, 5, 6].
  • Third iteration:

    • Compare nums1[i] with nums2[j] (which is 2).
    • nums1[i] is 3 which is greater than nums2[j].
    • Place nums1[i] in nums1[k], then decrement i to 1 and k to 2.
    • Now, nums1 looks like [1, 2, 3, 3, 5, 6].
  • Fourth iteration:

    • Compare nums1[i] (which is 2) and nums2[j] (which is 2).
    • They are equal, but it doesn't matter which one we choose. Here's we choose nums2[j].
    • Place nums2[j] in nums1[k], then decrement j to -1 and k to 1.
    • Now, nums1 looks like [1, 2, 2, 3, 5, 6].

Since j is now -1, we have placed all elements from nums2 into nums1. The elements from nums1 that have not yet been moved are already correctly placed because nums1 was sorted to begin with. Our merged array is [1, 2, 2, 3, 5, 6], which is sorted in non-decreasing order.

Solution Implementation

1from typing import List
2
3class Solution:
4    def merge(self, nums1: List[int], total_nums1: int, nums2: List[int], total_nums2: int) -> None:
5        """
6        Merges two sorted arrays, nums1 and nums2, into a single sorted array.
7        The first array nums1 has a size sufficient to hold the contents of both arrays.
8        The merge is done in-place.
9      
10        :param nums1: List[int], the first sorted array with extra space for nums2.
11        :param total_nums1: int, the number of valid elements in nums1.
12        :param nums2: List[int], the second sorted array to be merged into nums1.
13        :param total_nums2: int, the number of elements in nums2.
14        """
15        # Initialize pointers for nums1 and nums2 starting from the end of their valid elements
16        index_nums1, index_nums2 = total_nums1 - 1, total_nums2 - 1
17      
18        # Start filling nums1 from the end, to avoid overwriting elements of nums1 that are not yet merged
19        merge_index = total_nums1 + total_nums2 - 1
20      
21        # Merge in reverse order
22        while index_nums2 >= 0:
23            # If nums1 is not yet exhausted and the current element is larger than nums2's, place it in the current position
24            if index_nums1 >= 0 and nums1[index_nums1] > nums2[index_nums2]:
25                nums1[merge_index] = nums1[index_nums1]
26                index_nums1 -= 1  # Move the nums1 index backwards
27            else:
28                # Else, place element from nums2
29                nums1[merge_index] = nums2[index_nums2]
30                index_nums2 -= 1  # Move the nums2 index backwards
31            merge_index -= 1  # Move the merge index backwards
32
1class Solution {
2    // Merges two sorted arrays, nums1 and nums2, into a single sorted array.
3    public void merge(int[] nums1, int m, int[] nums2, int n) {
4        // Initialize pointers for nums1, nums2 and the merged array.
5        int indexNums1 = m - 1; // Pointer for the last element in the nums1's original part
6        int indexNums2 = n - 1; // Pointer for the last element in nums2
7        int mergedIndex = m + n - 1; // Pointer for the last element of merged array (end of nums1)
8
9        // Iterate over nums2 and nums1 from the end of both arrays
10        while (indexNums2 >= 0) {
11            // If nums1 is exhausted, or the current element in nums2 is larger
12            if (indexNums1 < 0 || nums1[indexNums1] <= nums2[indexNums2]) {
13                nums1[mergedIndex] = nums2[indexNums2]; // Place nums2's element in the merged array
14                indexNums2--; // Move to the next element in nums2
15            } else {
16                // The current element in nums1 is larger; place it in the merged array
17                nums1[mergedIndex] = nums1[indexNums1];
18                indexNums1--; // Move to the next element in nums1
19            }
20            mergedIndex--; // Move to the next position in the merged array
21        }
22        // No need to check the remaining elements of nums1, 
23        // if any left, since they are already in their sorted position.
24    }
25}
26
1class Solution {
2public:
3    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
4        // Initialize two pointers for the end of the two arrays and
5        // one pointer for the end of the merged array
6        int nums1Index = m - 1; // Pointer for the end of nums1
7        int nums2Index = n - 1; // Pointer for the end of nums2
8        int mergeIndex = m + n - 1; // Pointer for the end of the merged array (nums1)
9
10        // Iterate through nums1 and nums2 from the end until all elements from nums2 are inserted
11        while (nums2Index >= 0) {
12            // If there are still elements in nums1 and the current
13            // element of nums1 is larger than that of nums2
14            if (nums1Index >= 0 && nums1[nums1Index] > nums2[nums2Index]) {
15                // Place the element of nums1 in the correct position of the merged array
16                nums1[mergeIndex] = nums1[nums1Index];
17                nums1Index--; // Move the pointer of nums1 to the left
18            } else {
19                // Place the element of nums2 in the correct position of the merged array
20                nums1[mergeIndex] = nums2[nums2Index];
21                nums2Index--; // Move the pointer of nums2 to the left
22            }
23            mergeIndex--; // Move the pointer of the merged array to the left
24        }
25        // No need to copy the remaining elements of nums1, if any, since they are already in place.
26    }
27};
28
1// Merges two sorted arrays nums1 and nums2 into nums1 in sorted order.
2// The first m elements of nums1 contain the initial sorted elements
3// and nums1 has enough space to hold the additional elements from nums2.
4// The arguments n and m represent the number of elements in nums2 and nums1, respectively.
5function merge(nums1: number[], countNums1: number, nums2: number[], countNums2: number): void {
6    // Initialize pointers:
7    // lastNums1Index - Pointer for the last element in nums1's initial sorted part.
8    // lastNums2Index - Pointer for the last element in nums2.
9    // mergedIndex - Pointer for the last position in nums1 where we will place the merged element.
10    let lastNums1Index: number = countNums1 - 1;
11    let lastNums2Index: number = countNums2 - 1;
12    let mergedIndex: number = countNums1 + countNums2 - 1;
13
14    // Merge in reverse order to avoid overwriting elements in nums1 that have not been checked yet.
15    while (lastNums2Index >= 0) {
16        // Check and compare elements from nums1 and nums2.
17        // Place the larger element in the correct sorted position at the end of nums1.
18        nums1[mergedIndex--] = lastNums1Index >= 0 && nums1[lastNums1Index] > nums2[lastNums2Index]
19            ? nums1[lastNums1Index--] // Use the element from nums1 and decrement the pointer.
20            : nums2[lastNums2Index--]; // Use the element from nums2 and decrement the pointer.
21    }
22}
23

Time and Space Complexity

The given code has a time complexity of O(m + n) since it involves iterating over the elements of nums1 and nums2 in reverse order, where m and n are the lengths of the respective arrays. It's a single pass through the combined size of both arrays, hence the addition of m and n.

The space complexity of the code is O(1), as it only uses a constant amount of extra space. The merging is done in place and does not require any additional data structures that scale with the input size.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the relationship between a tree and a graph?


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More