Merge Sorted Array

Try to solve the Merge Sorted Array problem.

We'll cover the following

Statement#

Given two sorted integer arrays, nums1nums1 and nums2nums2, and the number of data elements in each array, mm and nn, implement a function that merges the second array into the first one. You have to modify nums1nums1 in place.

Note: Assume that nums1nums1 has a size equal to m+nm + n, meaning it has enough space to hold additional elements from nums2nums2.

Constraints:

  • nums1.length =m+n= m + n
  • nums2.length =n= n
  • 0≤m,n≤2000 \leq m, n \leq 200
  • 1≤m+n≤2001 \leq m + n \leq 200
  • −103≤-10^3 \leq nums1[i], nums2[j] ≤103\leq 10^3

Example#

The inputs will be two integer arrays and two integers representing the number of data elements in each array.

Created with Fabric.js 3.6.6 Output Sample example 1Input nums1 3 4 9 0 0 0 m = 3 nums2 1 2 7 n = 3 1 2 3 4 7 9

1 of 2

Created with Fabric.js 3.6.6 Output Sample example 2Input nums1 1 4 9 0 0 m = 3 nums2 1 76 n = 2 1 1 4 9 76

2 of 2

The zeroes at the end of nums1nums1 represent uninitialized integers. This additional space will be used to merge it with nums2nums2.

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Merge Sorted Array

1

What is the output if the following arrays and values of mm and nn are given as input?

nums1 = [1, 2, 7, 92, 0, 0, 0], m = 4

nums2 = [3, 4, 5], n = 3

A)

[1, 2, 3, 4, 5, 7, 92]

B)

[1, 2, 7, 92, 3, 4, 5]

C)

[3, 4, 5, 1, 2, 7, 92]

Question 1 of 20 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Initialize two pointers, p1p1 and p2p2, that point to the last data elements in nums1nums1 and nums2nums2, respectively.

Initialize a pointer pp, that points to the last element of nums1nums1.

If the value at p1p1 is greater than the value at p2p2, set the value at pp equal to p1p1 and decrement p1p1 and pp by 1.

Else, if the value at p2p2 is greater than the value at p1p1, set the value at pp equal to p2p2 and decrement p2p2 and pp by 1.

Continue the traversal until nums2nums2 is merged with nums1nums1.

Try it yourself#

Implement your solution in main.py in the following coding playground. We have provided useful code templates in the other file that you may build on to solve this problem.

Python
main.py
traversal.py
Input #1
Input #2
Input #3
Input #4
%0 node_01 1 node_11 2 node_21 3 node_31 0 node_41 0 node_51 0
Visualization for Input #1
Merge Sorted Array

K-way Merge: Introduction

Solution: Merge Sorted Array