Merge Two Sorted Arrays without Extra Space

Problem Statement

Given the sorted arrays $nums1[]$ and $nums2[]$ of sizes n and m in non-decreasing order. Merge without extra space in sorted, non-decreasing order such that nums1 contains the first n elements, and nums2 contains the last m elements.

Example

Example Explanation

The following two arrays are given :

Try to merge two sorted arrays without extra space such that the smallest n elements are present in the first array and the remaining m elements in the second array in a non-descending sorted manner.

After merging the two non-decreasing arrays :

The output should be :

Input/Output

Input :

There are four lines of input.

• The first line contains the value of 'n', which is the length of nums1.
• The second line contains n space-separated integers.
• The third line contains the value of 'm', which is the length of nums2.
• The fourth or final line contains m space-separated integers.

Output :

Print values of nums1 and nums2 after modifying them such that nums1 contains the first n elements and nums2 contains the last m elements.

Constraints

$nums1.length = n$ $nums2.length = m$ $1 <= m, n <= 200$ $1 <= m + n <= 200$ $-10^{9} <= nums1[i], nums2[j] <= 10^{9}$

Algorithm - 1 : Brute Force Approach

Algorithm :

• Step 1 :
  In the initial step, build an array 'merged_array' of size total_len, where total_len is the sum of the size of nums1 and nums2.
• Step 2 :
  Insert elements from nums1 and nums2 into the merged_array.
• Step 3 :
  Sort merged_array in non-decreasing order.
• Step 4 :
  Fill the first n elements from merged_array into nums1.
• Step 5 :
  Fill the remaining elements (last m elements) of the merged array into nums2.
• Step 6 :
  In the final step print the original arrays and the arrays formed after merging the 2 arrays.

Code Implementation :

C++ :

Java :

Python :

Input :

Output :

Complexity Analysis

Time Complexity :

• To traverse the first array we need $O(n)$ time.
• To traverse the second array we need $O(m)$ time.
• To traverse the merged array time complexity is $O(n+m)$.
• To sort the merged array time complexity will be $O((n+m)log(n+m))$.

So, the overall time complexity for this approach will be O((n+m)log(n+m)).

Space complexity :
Since we use extra space by building a new merged_array of size m+n the space complexity will be O(n+m).

Algorithm - 2 : Without Using Extra Space

Algorithm :

• Step - 1 :
  At the initial step iterate through nums1 using a for loop.
• Step - 2 :
  For every element in nums1 check if it is greater than the first element of nums2.
• Step - 3 :
  If condition satisfies sort nums2 in non-decreasing order.
• Step - 4 :
  Iterate through the loop and repeat the process till the last index of nums1.
• Step - 5 :
  In the final step print the original arrays and the arrays formed after merging the 2 arrays.

Code Implementation :

C++ :

Java :

Python :

Input :

Output :

Complexity Analysis

Time Complexity :
While iterating through nums1 of length n, nums2 of length m is also traversed for rearrangement. Hence, the time complexity for this approach is O(m * n).

Space complexity :
The space complexity to merge two sorted arrays without extra space using this approach is O(1).

Algorithm : 3 - Gap Method

Algorithm :

• Step - 1 :
  At the initial step calculate the gap as the ceil value of total_len/2, where total_len = m+n.
• Step - 2 :
  Assign values 0 and gap to pointers ptr1 and ptr2, respectively.
• Step - 3 :
  Iterate through m+n using the pointers.
• Step - 4 :
  Check if the value of location ptr2 is less than the value of location ptr1 points at.
• Step - 5 :
  Swap values, if the condition is satisfied.
• Step - 6 :
  After termination of the loop assign a new value to the gap using the 'nextGap' function.
• Step - 7 :
  Terminate the process when the value of gap becomes less than 0.
• Step - 8 :
  In the final step print the original arrays and the arrays formed after merging the 2 arrays.

Code Implementation :

C++

Java

Python

Input :

Output :

Complexity Analysis

Time Complexity :
Since the pointer iterates through 'total_len' the time complexity for this approach will be O(m+n).

Space complexity :
The space complexity to merge two sorted arrays without extra space using this approach is O(1).

Explore Scaler Topics Data Structures Tutorial and enhance your DSA skills with Reading Tracks and Challenges.

Learn More:

• Merge Two Sorted Arrays