Merge Sorted Array

excerpt: Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. tags: three-pointers

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has a size equal to m + n such that it has enough space to hold additional elements from nums2.

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]

Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Constraints

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

Thinking Process

 0 1 2 3 4 5
[1,2,3,0,0,0]
[2,5,6]
 0 1 2

index = 5 - 3 = 2

i = 2 to 0

  • Compare 6 and 3

  • Save 6 in last spot: [1,2,3,0,0,6]

  • Decrement k

  • Compare 5 and 3

  • Save 5 in the next spot pointed to by k [1,2,3,0,5,6]

  • Decrement k

  • Compare 2 and 3

  • Save 3 in the next spot pointed to by k [1,2,3,3,5,6]

  • Confused in this case, how should I copy the last number to the nums1?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def merge(nums1, m, nums2, n)
  i = nums1.size - 1
  j = n - 1
  k = m - 1
  
  while j >= 0
    if nums1[k] > nums2[j]
      nums1[i] = nums1[k]
      i -= 1
      k -= 1
    else
      nums1[i] = nums2[j]
      j -= 1
      i -= 1
    end
  end
end

Fails for the edge case: merge([2,0], 1, [1], 1)

Working Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def merge(nums1, m, nums2, n)
  i = m - 1
  j = n - 1
  k = m + n - 1
    
  while k >= 0
    if j < 0
      break
    end
        
    if i >= 0 && nums1[i] > nums2[j]
      nums1[k] = nums1[i]
      i -= 1
    else
      nums1[k] = nums2[j]
      j -= 1
    end
    
    k -= 1
  end
end

To merge two sorted arrays nums1 and nums2 into a single sorted array in-place, you can follow the steps below:

  1. Initialize Pointers: Create three pointers, one for the current position in nums1 (ptr1), one for the current position in nums2 (ptr2), and one for the current position in the final merged array (current).
  2. Start from the End: Initialize ptr1 to m - 1, ptr2 to n - 1, and current to m + n - 1.
  3. Compare and Merge: Compare the elements at ptr1 and ptr2. If nums1[ptr1] is greater, place it at current, else place nums2[ptr2] at current. Decrement the respective pointers and current.
  4. Handle Remaining Elements: If there are remaining elements in nums2, copy them to nums1.
  5. Finish: nums1 now contains the merged sorted array.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        ptr1, ptr2, current = m - 1, n - 1, m + n - 1

        # Merge nums1 and nums2 in descending order
        while ptr1 >= 0 and ptr2 >= 0:
            if nums1[ptr1] > nums2[ptr2]:
                nums1[current] = nums1[ptr1]
                ptr1 -= 1
            else:
                nums1[current] = nums2[ptr2]
                ptr2 -= 1
            current -= 1

        # If there are remaining elements in nums2, copy them to nums1
        while ptr2 >= 0:
            nums1[current] = nums2[ptr2]
            ptr2 -= 1
            current -= 1

Since you are iterating through the two given arrays once, the time complexity is (O(m + n)), where (m) and (n) are the lengths of the given arrays. The space complexity is (O(1)) as the operation is performed in-place.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# @param {Integer[]} nums1
# @param {Integer} m
# @param {Integer[]} nums2
# @param {Integer} n
# @return {Void} Do not return anything, modify nums1 in-place instead.
def merge(nums1, m, nums2, n)
  i = m - 1
  j = n - 1
  k = m + n - 1

    while k >= 0
       if j < 0
           break
       end

        if i >= 0 && nums1[i] > nums2[j]
            nums1[k] = nums1[i]
            i -= 1
        else
           nums1[k] = nums2[j]
            j -= 1
        end
        k -= 1
    end
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def merge_two_sorted_arrays(A: List[int], m: int, B: List[int], n: int) -> None:
    a, b, write_index = m-1, n-1, m + n - 1

    while b >= 0:
        if a >= 0 and A[a] > B[b]:
            A[write_index] = A[a]
            a -= 1
        else:
            A[write_index] = B[b]
            b -= 1

        write_index -= 1

Problem Classification

  1. Array Manipulation: The problem involves manipulating and modifying arrays. Understanding how to work with arrays, including accessing elements, updating elements, and understanding array indices is crucial to solving this problem.

  2. Sorting: The task is to merge two sorted arrays into a single sorted array. This falls into the broad category of sorting problems.

  3. Two-pointers Technique: The problem involves comparing elements from two arrays at a time, often referred to as a “two-pointers” or “two-iterators” technique. This approach is frequently used in array manipulation problems.

  4. In-Place Operations: The problem requires merging the second array into the first one without allocating additional space for another array. This is common in problems that require optimization of space complexity.

These classifications help narrow down the possible approaches and techniques used to solve this type of problem.

Language Agnostic Coding Drills

This provided code is a Python function to merge two sorted arrays. Given two sorted integer arrays A and B, the function merges B into A as one sorted array.

Here’s how we can break it down into smaller learning units:

  1. Arrays (or Lists in Python): Understanding the concept of arrays or lists in Python is crucial to this problem. This includes creating, accessing, and manipulating elements in an array.

  2. Variables and Data Types: There are integer variables in the code that keep track of indexes (a, b, write_index).

  3. Loops (While Loop): This code contains a while loop, which is used to iterate over the elements in arrays A and B.

  4. Conditional Statements (If and Else): There are conditional statements in this code to compare the current elements of A and B.

  5. Index Manipulation: The solution involves manipulating indices of two arrays to merge them in a sorted manner.

Problem-Solving Approach:

  1. Understand the problem: The task is to merge two sorted arrays. Given that the arrays are already sorted, we can leverage this fact in our solution to make the process more efficient.

  2. Define the problem requirements: Given two sorted integer arrays A and B, merge B into A as one sorted array.

  3. Break down the problem: The problem can be broken down into simpler tasks:

    • Track the current index for both arrays that we are comparing elements from.
    • Compare the current elements of A and B, and place the larger one at the current end of the merged array.
    • Repeat this until all elements in B are merged into A.

  4. Develop a solution: The pseudocode for the solution can be written as:

    • Start from the end of A and B, compare the current elements a and b.
    • If a > b, place a at the end of the merged array and move the pointer of A.
    • If b >= a, place b at the end of the merged array and move the pointer of B.
    • Repeat this process until all elements in B are merged into A.

  5. Test the solution: The solution should be tested with various inputs to ensure it covers all scenarios. Consider edge cases such as when one or both arrays are empty, and when all elements in B are larger or smaller than all elements in A.

Targeted Drills in Python

  1. Arrays (or Lists in Python):
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# Creating arrays
A = [1, 2, 3, 0, 0, 0]
B = [2, 5, 6]

# Accessing elements in an array
print(A[0])  # prints 1
print(B[1])  # prints 5

# Manipulating elements in an array
A[3] = B[0]  # assigns 2 to the fourth element in A
print(A)  # prints [1, 2, 3, 2, 0, 0]
  1. Variables and Data Types:
1
2
3
4
5

# Integer variables
m = len(A)
n = len(B)
a = m - 1
print(a)  # prints 3
  1. Loops (While Loop):
1
2
3
4
5

# Using a while loop to iterate over the elements in an array
i = len(A) - 1
while i >= 0:
    print(A[i])
    i -= 1
  1. Conditional Statements (If and Else):
1
2
3
4
5
6
7

# If and else statements
a = 5
b = 3
if a > b:
    print("a is greater than b")
else:
    print("a is less than or equal to b")
  1. Index Manipulation:
1
2
3
4
5
6

# Manipulating indices of an array
A = [1, 2, 3, 0, 0, 0]
B = [2, 5, 6]
a, b = len(A) - 1, len(B) - 1
A[a] = B[b]  # assigns the last element of B to the last element of A
print(A)  # prints [1, 2, 3, 0, 0, 6]

Problem Specific Drill:

Now let’s combine all of these concepts into a drill specific to the problem at hand:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def merge_two_sorted_arrays(A, m, B, n):
    a, b, write_index = m - 1, n - 1, m + n - 1

    while b >= 0:
        if a >= 0 and A[a] > B[b]:
            A[write_index] = A[a]
            a -= 1
        else:
            A[write_index] = B[b]
            b -= 1

        write_index -= 1

    return A

A = [1, 2, 3, 0, 0, 0]
m = 3
B = [2, 5, 6]
n = 3

print(merge_two_sorted_arrays(A, m, B, n))  # prints [1, 2, 2, 3, 5, 6]

This drill exercises all the necessary concepts and builds up to the final solution. Each concept is demonstrated in isolation and then integrated into the final solution.