Merge two sorted arrays without using extra space

Given two sorted arrayA and arrayB such that arrayA has enough void spaces in it to be able to accommodate arrayB in it. Void spaces in an array are denoted using INVALID_NUM. Write a program to merge arrayB into arrayA such that resulting array is a sorted array. The expected space complexity is O(1).  

For example, if arrayA = {-3, 5, INVALID_NUM, 7, INVALID_NUM, 10, INVALID_NUM, 11, INVALID_NUM} and arrayB = {-1, 2, 6, 12}
then arrayS should be modified to array - {-3, -1, 2, 5, 6, 7, 10, 11, 12}


Video coming soon!



Subscribe for more updates


Preparing for interviews? IDeserve team is here to help.




Algorithm/Insights

The algorithm to solve this problem is very similar to merge procedure of mergesort algorithm. First we move all valid elements of arrayA towards the end of it. For example, arrayA = {-3, 5, INVALID_NUM, 7, INVALID_NUM, 10, INVALID_NUM, 11, INVALID_NUM} is modified to {INVALID_NUM,INVALID_NUM,INVALID_NUM,INVALID_NUM,-3,5,7,10,11}. After this modification, k is initialized to 0, element arrayA[i] is compared with element arrayB[j] for values of 'i' starting from index of first valid element in arrayA up to size of arrayA and for all values of 'j' starting from 0 up to size of arrayB. If element arrayA[i] is less than element arrayB[j], arrayA[i] is copied to arrayA[k] otherwise arrayB[j] is copied to arrayA[k]. This compare and copy operation is done until all the elements from either arrayA or arrayB are compared and copied to arrayA. If after completion of this operation, there are still elements left in arrayB to be copied in arrayA then remaining elements from arrayB are copied towards the end of the arrayA.

Please checkout function inplaceMergeArrays(int[] arrayA, int[] arrayB) in code snippet for implementation details. The time complexity of this algorithm is O(n) with space complexity of O(1).

Please add comments below in case you have any feedback/queries.


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.nilesh;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Merging of two sorted arrays without using extra space (space complexity O(1))
 * @author Nilesh
 */

public class MergeSortedArraysInplace 
{
    final static int INVALID_NUM = 0;

    public void inplaceMergeArrays(int[] arrayA, int[] arrayB)
    {
        // move all elements of arrayA with valid values towards the end
        int validNumIndex = arrayA.length - 1;
        for (int i = arrayA.length - 1; i >= 0; i--)
        {
            if (arrayA[i] != INVALID_NUM)
            {
                arrayA[validNumIndex] = arrayA[i];
                validNumIndex -= 1;
            }
        }
        
        // i: index of first valid valued element in arrayA
        int i = validNumIndex + 1;
        int j = 0, k = 0;
        
        // fill-up arrayA starting from 0th index since this end of arrayA is free now
        while ((i < arrayA.length) && (j < arrayB.length))
        {
            if (arrayA[i] < arrayB[j])
            {
                arrayA[k++] = arrayA[i++];
            }
            else
            {
                arrayA[k++] = arrayB[j++];
            }
        }
        
        // copy any remaining elements of smaller array into larger one 
        while (j < arrayB.length)
        {
            arrayA[k++] = arrayB[j++];
        }
    }
    
    public static void main(String[] args) 
    {
        MergeSortedArraysInplace solution = new MergeSortedArraysInplace();
        
        
        int[] arrayA = {-3, 5, INVALID_NUM, 7, INVALID_NUM, 10, INVALID_NUM, 11, INVALID_NUM};
        int[] arrayB = {-1, 2, 6, 12};
        
        solution.inplaceMergeArrays(arrayA, arrayB);
        for (int i = 0;  i < arrayA.length; i++)
        {
            System.out.print(arrayA[i] + ", ");
        }
    }
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Nilesh More for compiling current post.

    Nilesh More

    Ninja Programmer