Merge two sorted arrays in constant extra space [Amazon]
Heuit
548
C++

1. Merge function from Merge sort
Time and space: O(n1+n2)

2. Idea of Insertion sort(Interview friendly)
Time : (n1* n2) space: O(1)


void adjust(vector<int>&v2, int n2){
	for(int i = 0; i < n2-1; ++i){
		if(v2[i] > v2[i+1]){
			swap(v2[i], v2[i+1]);
		}
	}
}
void merge(vector<int>&v1, vector<int>&v2, int n1, int n2){
	for(int i = 0; i < n1; ++i){
		if(v1[i] > v2[0]){
			swap(v1[i], v2[0]);
			adjust(v2, n2);
		}
	}
}
void printResult(vector<int>&v1, vector<int>&v2, int n1, int n2){
	fr(i, n1)cout<<v1[i]<<" ";
	fr(i, n2)cout<<v2[i]<<" ";
	cout<<endl; 
}
void solve(){
    int n1, n2;
    cin>>n1>>n2;
    vi v1(n1), v2(n2);
    fr(i,n1)cin>>v1[i];
    fr(i,n2)cin>>v2[i];

    merge(v1, v2, n1, n2);
    printResult(v1, v2, n1, n2);

}

3. Optimizing the previous approach(by converting second array to heap)(More Interview friendly)

Time: O((n1+n2)log(n2)) space: O(1), since we are not making new heap
Note: all(v2) is same as (v2.begin(), v2.end())

void merge(vector<int>&v1, vector<int>&v2, int n1, int n2){
	// build min heap out of v2
	make_heap(v2.begin(), v2.end(), greater<int>()); // O(n2)
	for(int i = 0; i < n1; ++i){ // n1 * log(n2)
		if(v1[i] > v2[0]){
			pop_heap(all(v2), greater<int>()); // log(n2)
			swap(v1[i], v2[n2-1]);
			push_heap(all(v2), greater<int>()); // log(n2)
		}
	}
	make_heap(all(v2)); // O(n2)
	sort_heap(all(v2)); // O(n2*alog(n2))
}
void printResult(vector<int>&v1, vector<int>&v2, int n1, int n2){
	fr(i, n1)cout<<v1[i]<<" ";
	// cout<<endl;
	fr(i, n2)cout<<v2[i]<<" ";
	cout<<endl; 
}
void solve(){
    int n1, n2;
    cin>>n1>>n2;
    vi v1(n1), v2(n2);
    fr(i,n1)cin>>v1[i];
    fr(i,n2)cin>>v2[i];

    merge(v1, v2, n1, n2);
    printResult(v1, v2, n1, n2);

}

4. Idea of shell sort(using gap: Most optimized and most non-trivial) (We're doomed, if asked)

Time: (n1+n2)log(n1+n2), log(n1+n2) since gap is getting halved each time
Space: O(1)

int nextGap(int n){
	if(n <= 1)return 0;
	return n/2 + n%2;
}
void merge(vector<int>&v1, vector<int>&v2, int n1, int n2){
	
	int gap = nextGap(n1+n2);
	while(gap){
		int i, j;
		// in 1st arrayonly
		for(i = 0; i + gap < n1; ++i){
			if(v1[i] > v1[i+gap]){
				swap(v1[i], v1[i+gap]);
			}
		}
		// in both array
		for(j = gap > n1 ? gap-n1 : 0; i<n1 && j<n2; ++i, ++j){
			if(v1[i] > v2[j]){
				swap(v1[i], v2[j]);
			}
		}
		// in 2nd array only
		if(j < n2){
			for(j = 0; j + gap < n2; ++j){
				if(v2[j] > v2[j+gap]){
					swap(v2[j], v2[j+gap]);
				}
			}
		}

		gap = nextGap(gap);
	}
}
void printResult(vector<int>&v1, vector<int>&v2, int n1, int n2){
	fr(i, n1)cout<<v1[i]<<" ";
	// cout<<endl;
	fr(i, n2)cout<<v2[i]<<" ";
	cout<<endl; 
}
void solve(){
    int n1, n2;
    cin>>n1>>n2;
    vi v1(n1), v2(n2);
    fr(i,n1)cin>>v1[i];
    fr(i,n2)cin>>v2[i];

    merge(v1, v2, n1, n2);
    printResult(v1, v2, n1, n2);

}
Comments (0)