[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)

Leetcode 992: Subarrays with K Different Integers

https://leetcode.com/problems/subarrays-with-k-different-integers/description/

Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.

(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)

Return the number of good subarrays of A.

Example 1:

Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

Example 2:

Input: A = [1,2,1,3,4], K = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

Note:

1. 1 <= A.length <= 20000
2. 1 <= A[i] <= A.length
3. 1 <= K <= A.length

Notes:

This question looks like a two-pointer sliding window problem. Left is the starting position. Once we reach the state of having K different integers, we need to know the last position of the first kind of number, which is label as i. Then there are (i - Left) number of string.

Now we can add the next number into account.

(1) If this number shows up previously, then we just need to update the last appearing position of it. The added number of string is still (i - Left);

(2) If this number is new element, then we need to remove the first kind of number (or the one with the smallest last position, newLeft). update Left to newLeft. update memorization, add (i - newLeft) into the final res

See the code below:

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& A, int K) {
        int res = 0, left = -1, i = 0;
        unordered_map<int, int> mp;//<num, indx>
        set<pair<int, int>> st;//<<indx, num>>
        for(; i<A.size(); ++i) {
            if(mp.size() == K) break;
            if(mp.count(A[i])) st.erase({mp[A[i]], A[i]});
            mp[A[i]] = i;
            st.insert({i, A[i]});
        }
        if(mp.size() < K) return res;
        res += st.begin()->first - left;
        for(; i<A.size(); ++i) {
            if(mp.count(A[i])) {
                st.erase({mp[A[i]], A[i]});
            }
            else {
                left = st.begin()->first;
                mp.erase(st.begin()->second);
                st.erase(st.begin());
            }
            mp[A[i]] = i;
            st.insert({i, A[i]});
            res += st.begin()->first - left;
        }
        return res;
    }
};

There is much clever solution found online, here is the link.

The key is using the results from a simple question.

Find the code below:

class solution {
public:
    int subarraysWithKDistinct(vector<int>& A, int K) {
        return atMostK(A, K) - atMostK(A, K - 1);
    }
private:
    int atMostK(vector<int>& A, int K) {
        int i = 0, res = 0;
        unordered_map<int, int> count;
        for (int j = 0; j < A.size(); ++j) {
            if (!count[A[j]]++) K--;
            while (K < 0) {
                if (!--count[A[i]]) K++;
                i++;
            }
            res += j - i + 1;
        }
        return res;
    }
};

Leetcode 392: Is Subsequence

https://leetcode.com/problems/is-subsequence/description/

Notes:

This question is an easy question. Using the so-called two-pointer method. The key is the follow-up question.

See the code below:

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int i = 0, j = 0;
        for(; j<t.size(); ++j) {
            if(s[i] == t[j]) ++i;
            if(i == s.size()) return true;
        }
        return i == s.size();
    }
};

Now let's look at the follow-up: now there are Billions of s. So we need to find a faster way than the above. One method is group and then binary search: group the index of the same kind of letter in t from small to high; then do a binary search to each letter in s. Or pre-processing t + binary search of s in t

See the code below:

class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> ids(26);//in the design, we can set ids as a private attribute
                                    //and can be initialized when instantiating one object
                                    //then call the
        for(int i=0; i<t.size(); ++i) {
            ids[t[i]-'a'].push_back(i);
        }
        int idx = -1;
        for(int i=0; i<s.size(); ++i) {
            int j = s[i] - 'a';
            auto it = upper_bound(ids[j].begin(), ids[j].end(), idx);//the first bigger than idx
            if(it == ids[j].end()) return false;
            idx = *it;
        }
        return true;
    }
};

Leetcode 727: Minimum Window Subsequence

https://leetcode.com/problems/minimum-window-subsequence/

Notes:

This question can be viewed as a follow up to Leetcode 76

The basic idea is to scan string s to match string t.

(1): when s[i] == t[j], both i and j update; otherwise, only i updates;

(2): when j == t.size(), meaning it is matched. Then we need to check back what is the minimum substring that fits the requirement.

(3): the method is scan back starting with position s[i]. Step(2) guarantees that T is subsequence of S[start ... i] ending with S[i], so we just need to do the reverse as the in Step (1). Once j is back to 0, meaning that it is found, then we can update the length.

(4): the update the i to i+1 (please note that i right now is already scanned back in Step 3.)

(5): repeat the above step util S is all scanned.

See the code below:

class Solution {
public:
    string minWindow(string S, string T) {
        int m = S.size(), n = T.size(), start = -1, minLen = INT_MAX, i = 0, j = 0;
        while (i < m) {
            if (S[i] == T[j]) {
                if (++j == n) {
                    int end = i + 1;
                    while (--j >= 0) {
                        while (S[i--] != T[j]);
                    }
                    ++i; ++j;//the above while loop runs 1 more backwards for both i and j
                    if (end - i < minLen) {
                        minLen = end - i;
                        start = i;
                    }
                }
            }
            ++i;
        }
        return (start != -1) ? S.substr(start, minLen) : "";
    }
};

There is another way to do it by applying dp:

dp[i][j] represents the initial position in S that S(dp[i][j], ... i) contains T as a subsequence.

The state transfer equation:

dp[i][j] = dp[i-1][j-1] when S[i] == T[j]
= dp[i-1][j] when S[i] != T[j]

If(dp[i][n] != -1) means there is fit. Then update the length.

See the code below:

class Solution {
public:
    string minWindow(string S, string T) {
        int m = S.size(), n = T.size(), start = -1, minLen = INT_MAX;
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, -1));
        for (int i = 0; i <= m; ++i) dp[i][0] = i;//initialization
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= min(i, n); ++j) {
                dp[i][j] = (S[i - 1] == T[j - 1]) ? dp[i - 1][j - 1] : dp[i - 1][j];
            }
            if (dp[i][n] != -1) {
                int len = i - dp[i][n];
                if (minLen > len) {
                    minLen = len;
                    start = dp[i][n];
                }
            }
        }
        return (start != -1) ? S.substr(start, minLen) : "";
    }
};

Leetcode 76: Minimum Window Substring

https://leetcode.com/problems/minimum-window-substring/description/

Notes:

The basic idea is counting and comparing with a sliding window or two-pointer method.

One detail is how to compare? If we compare the counting arrays or hash table directly, it will be costly. One better way is we just need a counting variable to count the total number of valid letters.
See the code below:

class Solution {
public:
    string minWindow(string s, string t) {
        int len1 = s.size(), len2 = t.size();
        if(len1 < len2) return "";
        int start = 0, len = 0;
        vector v1(256, 0), v2(256, 0);
        for(auto &a : t) ++v2[a];
        int i = 0, j = 0, ct = 0;
        while(i < len1 && j < len1) {
            ++v1[s[j]];//move right pointer
            if(v1[s[j]] <= v2[s[j]]) ++ct;//only count when the letter is valid;
            if(ct == len2) {
                while(i < j && v2[s[i]] < v1[s[i]]) --v1[s[i++]];//move left pointer
                if(len == 0 || len > j - i + 1) {
                    len = j - i + 1;
                    start  = i;
                }
            }
            ++j;
        }
        return s.substr(start, len);
    }
};

Leetcode 395: Longest Substring with At Least K Repeating Characters

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/description/

Solution 1: Brute Force

If we fix the left and gradually extend the right, then it is easy to prove that there are N + (N-1) + ... + 2 + 1 = N(N+1)/2 substrings. For each substring, we can scan them first and then determine whether it is valid or not. If yes, record the length for comparison, and save it if it is longer.

For determination whether each substring is valid or not, we can use a num_unique variable to record the counting situations. When a new letter is introduced, we update the num_unique by adding 1; when the count of one letter reaches to k, we update the num_unique by reducing 1. Thus, when num_unique = 0, it means all the letters satisfy the requirements: the counting is no less than k.

See the code below:

class Solution {
public:
    int longestSubstring(string s, int k) {
        int res = 0, len = s.size();
        if(s.size() < k) return res;
        if(k==1) return len;
        for(int left = 0; left < len; ++left) {
            vector ct(26, 0);
            int num_unique = 0;
            for(int right = left; right < len; ++right) {
                int idx = s[right] - 'a';
                ++ct[idx];
                if(ct[idx] == 1) ++num_unique;//add a new unique letter;
                if(ct[idx] == k) --num_unique;//reach k counts;
                if(num_unique == 0) res = max(res, right - left + 1);//when all letters reach or more than k counts;
            }
        }
        return res;
    }
};

So the time complexity is O(N^2) and space complexity is O(26) or O(1), are there better solutions in time complexity?

Solution 2: Recursion

Another way to think about this question is also straightforward: if we know the total number of one kind of letter is less than k for the whole string, then we can break the string into smaller strings at the positions of that kind of letter. This is one typical method in programming: break a question into a smaller similar questions, which is also called recursion.

See the code below:

class Solution {
public:
    int longestSubstring(string s, int k) {
        if(s.size() < k) return 0;
        vector<int> ct(26, 0);
        for(auto &a : s) ++ct[a-'a'];
        int idx = 0;
        while(idx < s.size() && ct[s[idx]-'a'] && ct[s[idx]-'a'] >= k) ++idx;
        if(idx == s.size()) return s.size();
        int left = longestSubstring(s.substr(0, idx), k);
        int right = longestSubstring(s.substr(idx+1), k);
        return max(left, right);
    }
};

The time complexity of the above code is still O(N^2). And there is a O(N) solution, which can be found below.

Solution 3: Categorization and Counting

There is one additional implicit constrain to the questions: there are only at most 26 kinds of letter in total. So for the valid substrings, they must satisfy:

(1) the number of each kind of letter is larger or equal to k;

(2) the total kinds of letter is between 1 and 26.

So we can scan the string with the above two constrains using two-pointer method. Basically, we find all the substrings that fit the above two constrains, then then find the one with the longest length.

See the code below:

class Solution {
public:
    int longestSubstring(string s, int k) {
        if(s.size() < k) return 0;
        int res = 0;
        for(int h=1; h<=26; ++h) {
            int i=0, j=0, unique = 0, noLessK = 0;
            vector<int> cts(26, 0);
            while(j<s.size()) {
             //   cout<<j<<endl;
                int b = s[j] - 'a';//move right idx and count
                if(cts[b] == 0) ++unique;
                ++cts[b];
                if(cts[b] == k) ++noLessK;
                if(unique > h) {
                    while(unique > h) {//move left idx to decrease total kinds of letter
                        int a = s[i] - 'a';   
                        if(cts[a] == k) --noLessK;
                        --cts[a];
                        if(cts[a] == 0) --unique;
                        ++i;
                    }
                }
                if(unique == noLessK) res = max(res, j-i+1);//satisfy two constrains
                ++j;
            }
        }
        return res;
    }
};

The time complexity is O(26*N) or O(N).

Follow ups or similar questions:

(1): what is the longest substring that fits the question?

(2): what is the total number of such substring?