[Start with Simple 1]: Two sorted arrays

In this post, we will start with a simple question, then gradually go to more complicated ones.

Let us look at the first question first.

Q1: How to merge two sorted arrays?

Notes:

Solution 1): Two pointers

we can use two pointers to each of the sorted arrays. Every time, we pick up the smaller one, then update the corresponding pointer by shifting one position forward until null. Time complexity O(N)   (or more specifically, O(N+M) in general). 

See the code below:

vector<int> merge(vector<int>& vs1, vector<int>& vs2) {
	vector<int> res;
	int i = 0, j = 0, m = vs1.size(), n = vs2.size();
	while(i<m && j<n) {
		if(vs1[i]<= vs2[j]) res.push_back(vs1[i++]);
		else res.push_back(vs2[j++]);
	}
	while(i<m) res.push_back(vs1[i++]);
	while(j<n) res.push_back(vs2[j++]);
	return res; 
}

Q2:  There are two sorted arrays, arr1 and arr2. We will pick up one element from arr1, arr1[i], and one element from arr2, arr2[j]. If arr1[i] > arr2[j], we call (arr1[i], arr2[j]) an awesome pair. The question is how many awesome pairs are there?

Example 1:

arr1 = [1, 2, 3],   arr2 = [1, 2, 3, 4, 5]

The the answer is 3.

Explanations:

if we pick up 1 from arr1, then there is 0 pair

if we pick up 2 from arr1, then there is 1 pair

if we pick up 3 from arr1, then there is 2 pair

Notes:

Solution 1): binary search

we can pick up one element from the first array, then do a binary search on the second one to find all the smaller elements in the second array. So the overall time complexity is O(N*log(N)).

See the code below:

int findAP(vector<int>& vs1, vector<int>& vs2) {
	int res = 0, n = vs1.size();
	for(int i=0; i<n; ++i) {
		int id = lower_bound(vs2.begin(), vs2.end(), vs1[i]) - vs1.begin();
		res += id;
	}
	return res; 
}

Solution 2): two pointers

actually we can do faster: the observation is that, if the elements in the second array are smaller than one element in the first array, then they are also smaller than the elements after that element in the first array.

So we use two pointers: one for the first one (p1), the other for the second one (p2). 

If p1 <= p2, we move p1 one position forward, and update the total pair count by adding the number of elements chosen from arr2 at this moment;

Else, we move p2 one position forward, and update the number of elements chosen from arr2 by adding 1;

The time complexity is O(N).

See the code below:

int findAP(vector<int>& vs1, vector<int>& vs2) {
	int res = 0, i= 0, j = 0, m = vs1.size(), n = vs2.size();
	while(i<m && j<n) {
		if(vs1[i] <= vs2[j]) {
			res += j;
			++i;
		} else {
			++j;
		}
	}
	while(i<m) {
		res += j;
		++i;
	}
	return res; 
}

This solution to this question can be used directly for a Leetcode hard question: 315 Count Smaller Numbers After Self (If have any question, please leave your comment below)

Q3:  We just follow the Q2, if we have the lower and upper bounds,  then how many pairs with the condition:   lower <= arr2[j] - arr1[i] <= upper?

Notes:

Solution 1): two pointers

The idea is the same: from the above condition, we can have:

1):   arr2[j] >= arr1[i] + lower;

2):   arr2[j] <= arr1[i] + upper;

Thus, we just need another two pointers for these two boundaries, one for the lower and the other for the upper. When the arr1[i] is shifting forward, the two boundaries need to shift correspondingly.

The time complexity is still O(N) 

(do not be confused by the while loop, the x, and y in the code below only scan one time of the arr2.)

See the code below:

int findAP(vector<int>& vs1, vector<int>& vs2, int lower, int upper) {
    int res = 0, i= 0, j = 0, x = 0, y = 0, m = vs1.size(), n = vs2.size();
    while(i<m && j<n) {
	while(x<n && vs1[i] + lower > vs2[x]) ++x;
        while(y<n && vs1[i] + upper >= vs2[y]) ++y;
	if(vs1[i] <= vs2[j]) {
	    res += y - x;
	    ++i;
	} else {
	    ++j;
	}
    }
    while(i<m) {
        while(x<n && vs1[i] + lower > vs2[x]) ++x;
	while(y<n && vs1[i] + upper >= vs2[y]) ++y;
	res += y - x;
	++i;
    }
    return res; 
}

This solution to this question can be used directly for another Leetcode hard question: 327 Count of Range Sum (If have any question, please leave your comment below)