Leetcode 1585: Check If String Is Transformable With Substring Sort Operations

 https://leetcode.com/problems/check-if-string-is-transformable-with-substring-sort-operations/description/

Notes:

There are only 10 types of letters, so one way is that we can handle them one by one.

One of the key observations for sorting sub-string (or any type of ascending sorting): the id of the largest element will no way get smaller (or the position cannot be moved forward in an ascending sort).

Based on this, we can just start with the largest letter, then the second largest one, ... until all done.

Let take '9' as an example, 

1): say there are 3 '9's in s and also 3 in t (if not, return false directly);

2): then the id of the 1st '9' in s should be <= the id of the 1st '9' in t (if not, return false. Why? since there is no way the id of the 1st '9' in s becomes smaller due to sorting (or there is no bigger letter than '9'));

3): then the id of the 2nd '9' in s should be <= the id of the 2nd '9' in t (if not, return false);

...

If all satisfy, then we can remove all '9' from s and t, then recursively run the same procedure but with a smaller size.

After removing all '9's, the next one is '8', ...

If all can be removed, return true.

[update: 2024/11/27] 

As commented @Kaisar below, there is a case ("891", "198") cannot pass.

We can just apply the same logic but with the reversed order: starting from '0', then the id of the smallest element will no way get larger.

When the results from both directions are true, return true. 

See the code below:

class Solution {
public:
    bool isTransformable(string s, string t) {
        string s1 = s, t1 = t;
        // check ids of elements from largest to smallest;
        for(char c='9'; c>='0'; --c) {
            vector<int> ids1, ids2;
            for(int i=0; i<s1.size(); ++i) {
                if(s1[i] == c) ids1.push_back(i);
                if(t1[i] == c) ids2.push_back(i);
            }
            if((int)ids1.size() != (int)ids2.size()) return false;
            for(int i=0; i<ids1.size(); ++i) {
                if(ids1[i] > ids2[i]) return false;
            }
            string s2 = "", t2 = "";
            for(auto &a : s1) {
                if(a < c) s2.push_back(a);
            }
            for(auto &a : t1) {
                if(a < c) t2.push_back(a);
            }
            s1 = s2;
            t1 = t2;
        }
        // check ids of elements from smallest to the largest;
        s1 = s, t1 = t;
        for(char c='0'; c<='9'; ++c) {
            vector<int> ids1, ids2;
            for(int i=0; i<s1.size(); ++i) {
                if(s1[i] == c) ids1.push_back(i);
                if(t1[i] == c) ids2.push_back(i);
            }
            if((int)ids1.size() != (int)ids2.size()) return false;
            for(int i=0; i<ids1.size(); ++i) {
                if(ids1[i] < ids2[i]) return false;
            }
            string s2 = "", t2 = "";
            for(auto &a : s1) {
                if(a > c) s2.push_back(a);
            }
            for(auto &a : t1) {
                if(a > c) t2.push_back(a);
            }
            s1 = s2;
            t1 = t2;
        }
        return true;
    }
};

Leetcode 1400: Construct K Palindrome Strings

 https://leetcode.com/problems/construct-k-palindrome-strings/description/

Notes:

This question seems not easy, but actually is not.

We just need to use one property of palindrome: at most there is one letter with odd count.

Thus, in order to form k palindromes, at most we have k letters with odd count.

If the size of string is smaller than k, there is no way to form k palindrome.

See the code below:

class Solution {
public:
    bool canConstruct(string s, int k) {
        int n = s.size(), res = 0;
        if(n<k) return false;
        if(n==k) return true;
        vector<int> ct(26, 0);
        for(auto &a : s) ++ct[a-'a'];
        for(auto &a : ct) {
            if(a & 1) ++res;
        }
        return res <= k;
    }
};

Leetcode 1558: Minimum Numbers of Function Calls to Make Target Array

 https://leetcode.com/problems/minimum-numbers-of-function-calls-to-make-target-array/description/

Notes:

This question can be solved greedily: 

1): if there is one element is odd, we need to reduce 1 to make it even; 

2): when all even, we can divide it by 2 

Since 2) is always faster than 1, so we need to do operation 2) whenever it is possible.

See the code below:

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int res = 0;
        bool largerThan0 = true, allEven = true;
        while(largerThan0) {
            largerThan0 = false;
            allEven = true;
            for(auto &a : nums) {
                if(a>0) largerThan0 = true;
                if(a&1) {
                    --a;
                    ++res;
                    allEven = false;
                }
            }
            if(largerThan0 && allEven) {
                for(auto &a : nums) a /= 2;
                ++res;
                largerThan0 = true;
            }
        }
        return res;
    }
};

Leetcode 1419: Minimum Number of Frogs Croaking

 https://leetcode.com/problems/minimum-number-of-frogs-croaking/description/

Notes:

This question can be solved in a greedy way.

We need to record some key information during scanning. 

For example, 

1): once we meet with a 'c', we should see whether there are available frog or not. If yes, no new frog is needed; otherwise, need a new frog;

2): once we meet with a 'r', we need to make sure there is at least one frog is yelling 'c'. If no, return -1;

if yes, need to update the counting on 'r' and 'c', respectively;

3): if 'o' or 'a', then it is similar to 2);

4): if 'k', similar to 2). but once difference is that: we only need to update the counting on 'a'. Then one more frog becomes available for the next round of yelling;

5): after scanning the string, we need to make sure all the frogs finish their yelling. This is can be done by scanning the counting of each letter. If all zero, it means all done; o/w, return -1.

6): return number of frog needed.

See the code below:

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        int n = croakOfFrogs.size(), res = 0, rm = 0;
        unordered_map<char, int> mp;
        for(auto &c : croakOfFrogs) {
            if(c=='c') {
                if(rm>0) --rm;
                else ++res;
                ++mp['c'];
            } else if(c == 'r') {
                if(!check(mp, 'c', 'r')) return -1;
            } else if(c == 'o') {
                if(!check(mp, 'r', 'o')) return -1;
            } else if(c == 'a') {
                if(!check(mp, 'o', 'a')) return -1;
            } else if(c == 'k') {
                if(!mp.count('a') || mp['a'] == 0) return -1;
                --mp['a'];
                ++rm;
            } else {
                return -1;
            }
        }
        for(auto &a : mp) {
            if(a.second > 0) return -1;
        }
        return res;
    }
private:
    bool check(unordered_map<char, int>& mp, char a, char b) {
        if(!mp.count(a) || mp[a] == 0) return false;
        --mp[a];
        ++mp[b];
        return true;
    }
};

Leetcode 621. Task Scheduler

https://leetcode.com/problems/task-scheduler/description/

Notes:

Let us look at the naive way first, then we can derive a mathematics formula from the first way.

This question can be solved in a greedy way: 

         1): first we need to counts the appearance times of each letter, and then put the counts into a priority queue.

         2): from the priority queue, we cal always get the elements with the maximum count. After popping out n times, (if there are less n types of elements, we have to use idles which are as the space keeper). Then push the popped elements back to the priority queue if their counts are still larger than 0 after minus 1 (since we have used one time).

         3): we increase the total counting for every element popping (including idles)

The time complexity is about O(m*n) since we need to pop out (m*n) times any way. The priority queue also involves sorting, but there are at most 26 different kinds of letters. So this sorting can be viewed as constant.

After having this solution, we can observe one rule: the maximum counting plays one of the key important role. Since we have to run out of it anyway. If the separator is n, then we have to run (maxCount - 1) * (n + 1) units for the first (maxCount -1) letters. The last repeated process does not need to maintain at least n different letters since there is no more letter after that.

If there is only one type of letter having the maximum counting, then only one letter remaining after (maxCount - 1) time repeating. But if there are m tied maximum counting, then there will be m letters in the last repeated pattern.

So the total units are (maxCount - 1) * (n + 1) + m, where m is the letter number with tied maximum counting

Then all the rest letter can be viewed as an idle: since in each repeated pattern, we can choose one from each type. If the total units is larger than the string size, we have to use real idle as space keeper; otherwise, there is no real idle needed.

The time complexity for the second way is O(m), where m is the size of the string.

See the code below:

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int freq = 0, rep = 0;
        vector<int> ct(26, 0);
        for(auto &a : tasks) {
            ++ct[a - 'A'];
            if(freq < ct[a-'A']) {
                freq = ct[a-'A'];
                rep = 1;
            } else if (freq == ct[a-'A']) ++rep;
        }
        return max((freq - 1) * (n + 1) + rep, (int)tasks.size());
    }
};

Leetcode 1562. Find Latest Group of Size M

https://leetcode.com/problems/find-latest-group-of-size-m/description/

Notes:

This question can be solved by greedy.

When one bit is labeled as 1, then we need to check its two sides: the left and the right. 

if the left has been labeled with a length of 1's, then we need to combine it with the current 1;

for the right, we need to do the same thing.

So we need a vector to memorize the length of 1's at each positions. Do we need to memorize this for all positions? 

The answer is no. We just need to record this information at the two end positions for a group of 1's.

For example, if we have 1's at position (or index) 2, 3, 4, we just need to label len[2] = len[4] = 3. Based on the question, all the element is valid, so 2, 3, 4 will not appear again. Therefore, we just need to deal with the boundaries of each group of 1's. To this example, the boundaries are 2 and 4.

Since the question is asking for the last time sting having length of 1 with m, we need a hash map to record the information for this. Since all the keys are in the range of 0 to n, then we can use a vector as a hash map.

See the code below:

class Solution {
public:
    int findLatestStep(vector<int>& arr, int m) {
        int n = arr.size(), res = -1;
        vector<int> len(n+2, 0), ct(n+1, 0);
        for(int i=0; i<arr.size(); ++i) {
            int a = arr[i], left = len[a-1], right = len[a+1];
            len[a] = len[a-left] = len[a + right] = left + right + 1;
            --ct[left];
            --ct[right];
            ++ct[left+right+1];
            if(ct[m]>0) res = i + 1;
        }
        return res;
    }
};

Leetcode 1567. Maximum Length of Subarray With Positive Product

https://leetcode.com/problems/maximum-length-of-subarray-with-positive-product/description/

Notes:

This question can be solved by greedy.

1): If meets with zero, we need to start the counting again from the zero position;

2): If meets with a positive value, the product will have the same sign as the previous product;

3): If meets with a negative value, then the product will have a opposite sign as the previous product.

If the updated product is positive, then we need to update the maxLen with the most current zero position;

If the updated product is negative, then we need to update the maxLen with the most current negative position.

So the code below:

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n = nums.size(), res = 0;
        for(int i = 0; i < n; ) {
            if(nums[i] == 0) {++i; continue;}
            int j = i, mostLeftNegativeIdx = j-1, p = 1;
            while(i < n && nums[i] != 0) {
                if(nums[i] < 0) p = -p;
                if(p > 0) res = max(res, i - j + 1);
                else {
                    if(mostLeftNegativeIdx > j-1) res = max(res, i - mostLeftNegativeIdx);
                    else mostLeftNegativeIdx = i;
                }
                ++i;
            }
        }
        return res;
    }
};

Facebook Phone Interview 1: Leftmost column index of 1

 In a binary matrix (all elements are 0 and 1), every row is sorted in ascending order (0 to the left of 1). Find the leftmost column index with a 1 in it.

Example 1:

Input:
[[0, 0, 0, 1],
 [0, 0, 1, 1],
 [0, 1, 1, 1],
 [0, 0, 0, 0]]
Output: 1

Example 2:

Input:
[[0, 0, 0, 0],
 [0, 0, 0, 0],
 [0, 0, 0, 0],
 [0, 0, 0, 0]]
Output: -1

Expected solution better than O(r * c).

Notes:

This question is mainly on the optimization.

The naive method is O(r*c), which is below the requirement.

One improvement is to use binary search for each row, since each row is sorted. Find the lower bound of each row, then choose the lowest one of them. The time complexity is O(r*(log(c)).

Can we do better?

The answer is yes (if r is very large), we can do a greedy search: 

starting from the top right corner, 

     if it is 1, we move to the left until the next element is 0; 

     then we just move down. 

     In the new row, we just repeat the above process until reach the boundary.

                if it is 0, we continue to move down; 

                if it is 1, we start to move left until the next element is 0.

at the end of the search, the current position is the left-most column having at least one 1.

The time complexity is O(r + c).

Why does greedy work?

The answer is that: for each step we have find a "left-most: column" so far; after finishing the whole search, we obtain the "left-most column" overall.

See the code below:

class Solution {
public:
    int mostLeftColumn(vector<vector<int>>& mt) {
    	if(!mt.size() || !mt.front().size()) return 0;
	int m = mt.size(), n = mt.front().size();
	int i = 0, j = n;
	while(i<m && j>0) {
	    if(mt[i][j-1] == 1) --j;
	    else ++i;
	}
	return j == n ? -1 : j;
    }
}

Leetcode 630: Course Schedule III

https://leetcode.com/problems/course-schedule-iii/description/

Notes:

This question is quick tricky.

One way to solve this problem is to sort the input by the ending time, which is like a deadline.

In general, we wish to choose classes with a shorter duration and a later deadline.

For the classes with the same deadline, we would to choose firstly the one with the shortest duration.

One variable is also needed to represent the current ending time: cur_time.

If cur_time + duration[i] <= deadline[i], we just need to place  duration[i] into a set;

otherwise, if duration[i] < *set.rbegin() (the last element in set), we just need to replace the last element by duration[i].

Why does this greedy way work?

1): since duration[i] is shorter (and the deadline may be later as well), thus it is definitely a better choice than *set.rbegin().

2): if we choose duration[i], we cannot choose *set.rbegin(), since the sum time is beyond the deadline;

3): so we have to choose one of them, which is duration[i].

Now is the key, can we simply place duration[i] into the set without checking its validity?

The answer is Yes. Before duration[i]，all the elements inside the set satisfy the constrain: sum time <= deadline. Now after the switch, the sum time becomes smaller, and the deadline becomes no smaller. So the constrain still hold automatically. And it is still the optimal solution.

In one word, once we meet with a solution with a shorter duration and a later deadline, and it cannot fit in with the current sum time, we need to replace the longest duration one already chosen by the new one with a shorter duration.

See the code below:

class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        sort(begin(courses), end(courses), [](auto &a, auto &b) {return a[1] < b[1];});
        multiset<int> st;
        int time = 0;
        for(int i=0; i<courses.size(); ++i) {
            if(time + courses[i][0] <= courses[i][1]) {
                st.insert(courses[i][0]);
                time += courses[i][0];
            }
            else {
                if(st.size() && *st.rbegin() > courses[i][0]) {
                    time += courses[i][0] - *st.rbegin();
                    st.erase(--st.end());
                    st.insert(courses[i][0]);
                }
            }
        }
        return st.size();
    }
};

The code can be simplified further using a priority_queue.

See the code below:

class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        sort(begin(courses), end(courses), [](auto &a, auto &b) {return a[1] < b[1];});
        priority_queue<int> pq;
        int time = 0;
        for(auto &a : courses) {
            pq.push(a[0]);
            time += a[0];
            if(time > a[1]) {
                time -= pq.top();
                pq.pop();
            }
        }
        return pq.size();
    }
};

Leetcode 910: Smallest Range II

https://leetcode.com/problems/smallest-range-ii/description/

Notes:

This question is a very tricky one.

Let start with two elements, [A, B], and A <= B. Then what should we do to obtain the minimum of the largest difference?

A can becomes A-K or A+K, and B becomes B-K or B+K.

If we choose the changes with the same direction (either +K or the -K), the largest difference is still B - A.

If we choose different different directions: we have to choose A + K, and B - K, in order to have a smaller largest difference. And the difference is max(A + K, B - K) - min(A + K, B - K).

So the overall minimum largest difference is min(B - A, max(A + K, B - K) - min(A + K, B - K)).

One of the key observations is that: in order to obtain the minimum of the possible largest differences, the smaller elements need to add K, and the larger elements need to minus K.

So now we have [A, B, C, D] as a sorted array.

Similar to the previous example, if we choose the same change, then the largest difference is still D - A.

If we separate the sorted array into two part: the smaller part and the larger part. Let say, [A, B] and [C, D]

then based on the above observation, the smaller part needs to add K, and the larger part needs to minus K, to obtained possible smaller largest difference.

So the smaller part becomes [A + K, B + K], and the larger part becomes [C - K, D - K].

In order to obtain the minimum largest difference, we need to find the largest of the largest elements, and the minimum of the smallest elements.

The former is max(B+K, D-K), and the latter is min(A+K, C-K).

So the global minimum largest difference is min(D - A, max(B+K, D-K) - min(A+K, C-K)).

Actually, we can split the array into two parts at any position from (1, to n-1), if there are n elements.

So the general formula is:

1): sort the array;

2): the minimum largest difference is

min(largestV - smallestV, max(V[i-1] + K, largestV - K) - min(V[i] - K, smallestV + K)), for i from 1 to n.


Thus, this question can be solved greedily, and TC is O(NlogN) and SC is O(1).

See the code below:

class Solution {
public:
    int smallestRangeII(vector<int>& A, int K) {
        sort(A.begin(), A.end());
        int res = A.back() - A.front();
        for(int i=1; i<A.size(); ++i) {
            int mn = min(A.front() + K, A[i] - K), mx = max(A[i-1] + K, A.back() - K);
            res = min(res, mx - mn);
        }
        return res;
    }
};

Leetcode 1282: Group the People Given the Group Size They Belong To

https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/description/

Notes:

The first step we need to category the elements based on the group size of the group they belong to.

Then the next step we just group the elements based on their group sizes.

Greedy can solve it, since there is no other requirements.

See the code below:

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> res;
        unordered_map<int, vector<int>> mp;
        for(int i=0; i<groupSizes.size(); ++i) mp[groupSizes[i]].push_back(i);
        for(auto &a : mp) {
            int i= 0, key = a.first;
            auto vs = a.second;
            while(i<vs.size()) {
                vector<int> t;
                while(t.size() < key) {
                    t.push_back(vs[i]);
                    ++i;
                }
                res.push_back(t);
            }
        }
        return res;
    }
};

Leetcode 1256: Encode Number

https://leetcode.com/contest/biweekly-contest-13/problems/encode-number/

Notes:

The key is to find the rules.
The number is encoded firstly with 2^0 + 2^1 + 2^2 + ... + 2^n, then the remainder is encoded into binary 0 or 1.

For example, n = 6.

The first step: n = 2^0 + 2^1 + 3. So the remainder is 3.

Then convert the remainder 3 to "11".

Let us see another example, n = 7.

The first step: n = 2^0 + 2^1 + 2^2. Then the remainder is 0 in this case.

One way to solve this problem, we can always take the last term, then convert it into binary form. From the last term, we can also determine the number of digit in the final binary result. For example, for n = 7, the last term is 2^2, so the final result should have 3 digit.

See the code below:

class Solution {
public:
    string encode(int num) {
        long sum = 0, indx = 0;
        while(sum + pow(2, indx) < (long) num) {
            sum += (long) pow(2, indx);
            ++indx;
        }
        num -= sum;//the last term
        string res = "";
        while(indx > 0) {//number of digits in the binary form
            res.push_back(num%2+'0');
            num /= 2;
            --indx;
        }
        if(num>0) res.push_back('0');//corner case, for example n= 7 vs n = 8
        reverse(res.begin(), res.end());
        return res;
    }
};

Leetcode 874: Walking Robot Simulation

https://leetcode.com/problems/walking-robot-simulation/description/

Notes:

This question is pretty straightforward, as labeled as easy.

The first step, we can put all the obstacles into a set. In this way, we can easily to tell whether it is a obstacle or not.

The second, we need a variable to represents the direction. There are four directions: north, east, south, and west, which can be labeled by 0, 1, 2, and 3, respectively.

Then turn left can be updated by (d + 3) % 4, and turn right can be updated as (d + 1)%4.

When d = 0, the x is updated by + 0, and y is updated by + 1;
when d = 1,        x                       + 1,                                 + 0;
when d = 2,        x                       + 0,                                 -  1;
when d = 3,        x                       - 1,                                 + 0;

Thus, we can simply these by using a one-dimensional direction array.

See the code below:

class Solution {
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        int res = 0;
        set<vector<int>> ob;
        for(auto &a : obstacles) ob.insert(a);
        int x = 0, y = 0, d = 0;
        vector<int> dirs={0, 1, 0, -1, 0};
        for(auto &a : commands) {
            if(a == -2) d = (d + 3)%4;
            else if(a == -1) d = (d + 1)%4;
            else {
                for(int i=0; i<a; ++i) {
                    if(ob.count({x + dirs[d], y + dirs[d+1]})) break;
                    else {
                        x += dirs[d];
                        y += dirs[d+1];
                    }
                    res = max(res, x*x + y*y);
                }
            }
        }
        return res;
    }
};

Lintcode 617: Maximum Average Subarray II

https://www.lintcode.com/problem/maximum-average-subarray-ii/note/171180

Description

中文English

Given an array with positive and negative numbers, find the maximum average subarray which length should be greater or equal to given length k.

It's guaranteed that the size of the array is greater or equal to k.

Have you met this question in a real interview?  

Example

Example 1:

Input:
[1,12,-5,-6,50,3]
3
Output:
15.667
Explanation:
 (-6 + 50 + 3) / 3 = 15.667

Example 2:

Input:
[5]
1
Output:
5.000

Notes:

This question is not an easy question, but greedy can solve it.

One way to think about this question is that: let's say we are now at the ith element position. If we put the ith element into consideration, we will have i more subarrays ending with the ith element. But we only care about the ones with a length no less than k.

So just need to record the previous sum results ending with the (i-1)th element and the corresponding length (since we need the average of them). Then update these results in both sum and length: sum will be added by nums[i], and length will be added by 1. And we will have a new subarray with size of k ending at the ith element. So we also need to take this into account.

One improvement is that, we can maintain a decreasing array in the sum. Since that the subarrays with the sum is smaller and the length is longer cannot give a larger average. So them can be ruled out directly.

During the scanning, we update the maximum average.

See the code below:

class Solution {
public:
    /**
     * @param nums: an array with positive and negative numbers
     * @param k: an integer
     * @return: the maximum average
     */
    double maxAverage(vector<int> &nums, int k) {
        // write your code here
        //sum: the sum of the last k elements ending with the (i-1)th element;
        double res = 0, sum = 0;
        int len = nums.size();
        stack<pair<double, double>> sk;
        for(int i=0; i<k; ++i) sum += (double) nums[i];
        res = sum/(double)k;
        sk.push({sum, k});
        for(int i=k; i<len; ++i) {
            sum += (double)nums[i] - (double)nums[i-k];
            vector<pair<double, double>> vs;
            while(sk.size()) {
                vs.push_back(sk.top());
                sk.pop();
            }
            for(auto &a : vs) {
                a.first += (double) nums[i];
                a.second += 1;
            }
            vs.push_back({sum, k});
            for(auto &a : vs) {
                auto t = a.first/a.second;
                if(res < t) res = t;
                if(sk.empty() || sk.top().first/sk.top().second > t) sk.push(a);
                else {
                    while(sk.size() && sk.top().first/sk.top().second <= t) sk.pop();
                    sk.push(a);
                }
            }
        }
        return res;
    }
};

Follow up:

This question can be modified a little bit: what is the maximum subarray sum with the size of the subarray no less than k?

The idea is very similar to the above one, but it is much easier to code, since we just need to save the largest sum from all previous subarray ending with the (i-1)th element.

Leetcode 321: Create Maximum Number

https://leetcode.com/problems/create-maximum-number/description/

Notes:

This question is hard question, as labeled.

My first method is using memorization, memo[i][j][k] represents the largest new arr with size of k by using elements starting of i-th in arr1 and j-th in arr2. But it quickly receive TLE.

It turns out it can be solved greedily. After decomposing it into two simpler sub-problems, this question becomes not that hard.

1): find a largest subsequence with a size of k from a given array;

2): merge two given arrays to form the largest sequence (including all elements).

Both sub-questions above are not hard to implemented (maybe the second one need to deal with a specific case when the first elements are equal, but it is still not hard to deal with with a short comparison function, see below).

See the code below:

class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int m = nums1.size(), n = nums2.size();
        vector<int> res(k);
        for(int i=max(0, k-n); i<=min(k, m); ++i) {
            vector<int> v1 = find(nums1, i), v2 = find(nums2, k-i);
                                          //find i from nums1, find (k-i) from nums2
            vector<int> nt = merge(v1, v2);
            if(larger(nt, 0, res, 0)) res = nt;
        }
        return res;
    }

private:
    vector<int> find(vector<int> &v, int k) {//find largest sequence with k elements;
        vector<int> res(k);
        int len = v.size();
        for(int i=0, j=0; i<len; ++i) {
            while(len-i+j>k && j>0 && res[j-1] < v[i]) --j;
            if(j<k) res[j++] = v[i];
        }
        return res;
    }

    bool larger(vector<int> &v1, int i, vector<int> &v2, int j) {//very useful comp function
        while(i<v1.size() && j<v2.size() && v1[i] == v2[j]) {
            ++i;
            ++j;
        }
        return j == v2.size() || (i < v1.size() && v1[i] > v2[j]);
    }

    vector<int> merge(vector<int> &v1, vector<int> &v2) {//merge two arrays into the largest one;
        int m = v1.size(), n = v2.size();
        vector<int> res(m+n);
        for(int i=0, j=0, k = 0; i<v1.size() || j <v2.size(); ++k) {
            res[k] = larger(v1, i, v2, j) ? v1[i++] : v2[j++];
        }
        return res;
    } 
};

There is another way to implement the find (vector<int>, int) function.

vector<int> find(vector<int> &v, int k) {//find k elements which gives the largest value;
        vector<int> res(k);
        int len = v.size();
        if(!k && len < k) return res;
        if(len == k) return v;
        int left = 0, right = len - k, i = 0;
        while(i < k) {
            int idMax = left;//initialization
            for(int i=left; i<=right; ++i) {
                if(v[i] > v[idMax]) idMax = i;
            }
            res[i++] = v[idMax];
            left = idMax + 1;//shift search range
            ++right;
        }
        return res;
    }

Follow-up: all the questions can be converted into finding the largest string sequence with strings.

Hackerrank 01: Jumping on the Clouds

https://www.hackerrank.com/challenges/jumping-on-the-clouds/problem?h_l=interview&h_r=next-challenge&h_r=next-challenge&h_v=zen&h_v=zen&page=9597&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=warmup

Notes:

An interesting question. The key is: can you make your code cleaner?

See one of example below:

int jumpingOnClouds(vector<int> c) {
    int res = 0;
    for(int i=0; i+1<c.size(); ) {//only need to reach the last one;
        if(i+2<c.size() && c[i+2] == 1) ++i;//can only jump one step;
        else i += 2;//jump two steps;
        ++res;
    }
    return res;
}

Leetcode 1042: Flower Planting With No Adjacent

https://leetcode.com/problems/flower-planting-with-no-adjacent/description/

Note:

• 1 <= N <= 10000
• 0 <= paths.size <= 20000
• No garden has 4 or more paths coming into or leaving it.
• It is guaranteed an answer exists.

Notes:

This question seems not easy, but actually it can be solved in a greedy way.

The first step is to build a graph with adjacent elements. Then is the key: for each element i or the ith garden, we need to check its neighbors (less than 4). If they have been planned with flowers, we cannot plan that kind of flower in ith. Otherwise, we can.

See the code below:

class Solution {
public:
    vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {
        vector<int> res(N, 0);
        vector<vector<int>> g(N);
        for(auto &a : paths){
            g[a[0]-1].push_back(a[1]-1);
            g[a[1]-1].push_back(a[0]-1);
        }
        for(int i=0; i<N; ++i){
            vector<int> used(5, 0);
            for(auto &a : g[i]) used[res[a]] = 1;//if used, label as 1;
            for(int fl = 1; fl <5; ++fl) {
                if(!used[fl]) {res[i] = fl; break;}
            }
        }
        return res;
    }
};

Leetcode 1057: Campus Bikes

https://leetcode.com › problems › campus-bikes

On a campus represented as a 2D grid, there are N workers and M bikes, with N <= M. Each worker and bike is a 2D coordinate on this grid.

Our goal is to assign a bike to each worker. Among the available bikes and workers, we choose the (worker, bike) pair with the shortest Manhattan distance between each other, and assign the bike to that worker. (If there are multiple (worker, bike) pairs with the same shortest Manhattan distance, we choose the pair with the smallest worker index; if there are multiple ways to do that, we choose the pair with the smallest bike index). We repeat this process until there are no available workers.

The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Return a vector ans of length N, where ans[i] is the index (0-indexed) of the bike that the i-th worker is assigned to.

Example 1:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]
Explanation: 
Worker 1 grabs Bike 0 as they are closest (without ties), and Worker 0 is assigned Bike 1. So the output is [1, 0].

Example 2:

Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
Output: [0,2,1]
Explanation: 
Worker 0 grabs Bike 0 at first. Worker 1 and Worker 2 share the same distance to Bike 2, thus Worker 1 is assigned to Bike 2, and Worker 2 will take Bike 1. So the output is [0,2,1].

Note:

1. 0 <= workers[i][j], bikes[i][j] < 1000
2. All worker and bike locations are distinct.
3. 1 <= workers.length <= bikes.length <= 1000

Notes:

This question can be solved greedily.  The total size of the data points are 1000 * 1000. We need to calculate the distances between any pair of (worker, bike), then sort them based on a): distance, b): worker index; c): bike index. Then we assign the (worker, bike) pair from the left to right.

See the code below:

class Solution {
public:
    vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        int m = workers.size(), n = bikes.size();
        vector<int> res(m, -1);
        vector<vector<int>> dt;
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                int dis = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]);
                dt.push_back({dis, i, j});
            }
        }
        sort(dt.begin(), dt.end(), [](auto &a, auto &b){return a[0]<=b[0] && a[1]<=b[1] && a[2]<=b[2];});
        vector<int> assignedW(m, 0), assignedB(n, 0);
        int count = 0;
        for(auto &a : dt) {
            if(!assignedW[a[1]] && !assignedB[a[2]]) {
                res[a[1]] = a[2];
                assignedW[a[1]] = 1;
                assignedB[a[2]] = 1;
                ++count;
            }
            if(count == m) break;
        }
        return res;
    }
};

Leetcode 316: Remove Duplicate Letters

https://leetcode.com/problems/remove-duplicate-letters/description/

Notes:

This question is same as Leetcode 1081, which essentially asks for the same thing.

The native response is to find the smaller[i] at the most-left position first. But before the smaller s[i], when we meet with a larger letter, we need to know whether there are still some in the remaining string after the smaller[i]. If true, we can simply ignore the larger one temporally since there are still some in the remaining part.

How do we know whether there are still some in the remaining string after the smaller[i]? One way is that we can count the number of each letter firstly. Then as scanning through the string, we know exactly how many are left to each letter.

See the code below:

class Solution {
public:
    string removeDuplicateLetters(string s) {
        string res = "";
        vector<int> ct(26, 0), used(26, 0);
        for(auto &a : s) ++ct[a-'a'];
        for(auto &a : s) {
            --ct[a-'a'];
            if(used[a-'a']++ >0) continue;//once already in the res, no need to run again
            while(res.size() && res.back() > a && ct[res.back() - 'a']) {
                used[res.back() - 'a'] = 0;//once pop, is not in the res anymore
                res.pop_back();
            }
            res.push_back(a);
        }
        return res;
    }
};

Another way is to solve this problem recursively: Scan the array greedily, we need to localize the most-left smallest s[i]. But as analyzed above, the requirement for continuing the scanning of the string is that, there are still some in the remaining part of the string. Once this condition become non valid, we can

1): put s[i] into the answer;
2): remove all the elements before s[i]; (why? because there are still some after s[i])
3): remove all the rest s[i] in the remaining string;
4): recursive check the remaining string.

See the code below:

class Solution {
public:
    string removeDuplicateLetters(string s) {
        if(s.size() < 2) return s;
        vector<int> ct(26, 0);
        for(auto &a : s) ++ct[a-'a'];
        int pos = 0;
        for(int i=0; i<s.size(); ++i) {
            if(s[i] < s[pos]) pos = i; //the most-left smallest s[i];
            if(--ct[s[i]-'a'] == 0) break; //no more left in the remaining string.
        }
        for(int i=pos+1; i<s.size(); ++i) {//remove extra s[i]
            if(s[i] == s[pos]) {
                s.erase(i, 1);
                --i;
            }
        }
        return s[pos] + removeDuplicateLetters(s.substr(pos+1));
    }
};

The time complexity of the above recursive code is till O(N) or O(26*N). (each letter at most check 1 time)