Merge two special arrays O(n) Code

Merge two special arrays with given conditions. 

Amazon Interview (May 2012).

 

 Problem Statement

Given two arrays having some elements in common, write a program to merge them such that all the elements occurring before common elements in both arrays also lie before common elements in merged array also and common element occurs only once in merged array.
Array can contain both alphabets and integers.
The elements lying before common element of both arrays can appear in any order in merged array.
Write a O(n) time complexity code.
Ex. A = [z,a,b,c,d,e,f]
       B = [k,g,a,h,b,f]
   Ans = [z,k,g,a,h,b,c,d,e,f]

Algorithm

1) Put elements of one array in hash-table.
2) Start incrementing pointer in 2nd array from 1 to n, if the element lie in hash-table put all elements before it in 1st array into the merged array else put this element into merged array.
3) Put any remaining elements into the merged array

If you have a different approach in mind, please share it in comments section for our readers.

Solution

import java.util.Map;
import java.util.HashMap;

class Solution
{

public static void main(String arg[])
{
char a[] = arg[0].toCharArray();
char b[] = arg[1].toCharArray();
char c[] = new char[a.length+b.length];
merge(a,b,c);
String s = new String(c);
System.out.println(s);
}

private static void merge(char a[], char b[], char c[]) {

Map<Character, Integer> m1 = new HashMap<Character, Integer>();

int i,j,k,l;

for(i=0;i<a.length;i++)
    m1.put(a[i],i);
       
l=0;i=0;j=0;
while(j<b.length) {
   
    if(m1.containsKey(b[j])) {
   
        k = m1.get(b[j]);
        while(i<=k)
            c[l++] = a[i++];
        j++;
    }
    else c[l++] = b[j++];
}
while(i<a.length)
    c[l++] = a[i++];
   
}
}   

Time Complexity: 

O(2n+m) where n is size of first array and m is size of second array. We travel first array twice once while putting its elements into merged array and second time while merging, therefore 2n for first array.



If you find this blog somewhat helpful, please give a +1.