Merge two sorted arrays in O(1) space

Posted by N.K. Chauhan on Mar 31, 2024

Given two sorted arrays of length n1 and n2 in ascending order, a1 [] and a2 [].

Merge them in sorted order so that a1[] contains the first n1 elements and a2[] contains the last n2 elements.

Input: a1[] = {1, 3, 5, 7}, a2[] = {0, 2, 6, 8, 9}
Output: a1[] = {1,3,5,7} a2[] = {0,2,6,8,9}

Input: a1[] = {10, 12}, a2[] = {5, 18, 20}
Output: a1[] = {5,10} a2[] = {12,18,20}


Solutions

Method 1: In O(n1*n2) time and O(1) space

In this approach, we iterate the first array a1[] from left to right and whenever we encounter an element that is greater than the first element of a2, i.e, a1[i] > a2 [0], we just swap it and rearrange a2[] in a sorted manner.

Complexity

The time complexity of this solution is O(n1*n2) and space complexity is O(1).

Related


Find maximum and minimum element of an array

Maximum Product Subarray (Modified Kadane's Algorithm)

Alternating +ve & -ve in array in O(1) time (maintaining order)

Find largest sum contiguous sub-array (Kadane's Algorithm)

Find duplicates in O(n) time and O(1) extra space

Segregate 0s and 1s in an array (Sort an array of 0s and 1s)

Program to right rotate an array by 'k' elements

Find duplicates in O(n) time and O(n) extra space.

Minimize the difference between the heights of smallest and highest tower

Segregate 0s, 1s and 2s in an array (Sort an array of 0s, 1s and 2s)

Move all negative numbers to beginning of the array