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].

1while j >= 0:
2    if i >= 0 and nums1[i] > nums2[j]:
3        nums1[k] = nums1[i]
4        i -= 1
5    else:
6        nums1[k] = nums2[j]
7        j -= 1
8    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.

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

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.