Lintcode 912: Best Meeting Point

https://www.lintcode.com/problem/best-meeting-point/description

Notes

This question can be viewed as a follow up of this question Leetcode 462. Minimum Moves to Equal Array Elements II.

The only difference is that the current question is a 2D case, instead of 1D.

So we just can separate it into two 1Ds. Why can we do this?

Because we need to calculate the Manhattan distance, which is the linear sum of 2 directions.

Once we record the x and y coordinates separately, we can treat it as Leetcode 462.

Leetcode 462 can be solved by binary search for a "u" shape sorted list.

The argument is listed below:

Let say the answer is in the range of [left, right].

Define mid = left + (right - left) / 2;

If dis(mid) < dis(mid-1), then the answer should be in [mid, right];
else, it should be in [left, mid-1].

See the code below:

class Solution {
public:
    int minTotalDistance(vector<vector<int>> &grid) {
        int res = 0;
        if(!grid.size() || !grid.front().size()) return res;
        int m = grid.size(), n = grid.front().size();
        vector<int> xs, ys;
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                if(grid[i][j] == 1) {
                    xs.push_back(i);
                    ys.push_back(j);
                }
            }
        }
        int x = f1(xs, 0, m-1), y = f1(ys, 0, n-1);
        return cal(xs, x) + cal(ys, y);
    }

private:
    int f1(vector<int>& vs, int x, int y) {
        if(x==y) return x;
        if(x+1 == y) {
            return cal(vs, x) < cal(vs, y) ? x : y;
        }
        int mid = x + (y - x) / 2;
        if(cal(vs, mid) < cal(vs, mid-1)) return f1(vs, mid, y);
        return f1(vs, x, mid-1);
    }
    int cal(vector<int>& vs, int v) {
        int res = 0;
        for(auto &a : vs) res += abs(a - v);
        return res;
    }
};

Leetcode 1300: Sum of Mutated Array Closest to Target

https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/description/

Notes:

This question is designed for binary search. Why?

Let say the answer is in a range of [left, right], then we can choose mid = left + (right - left) / 2.

Then we can compare val = mid and  val = mid - 1. If mid gives a better (or closer to target) than mid - 1, then we can say that the answer should be in the range of [mid, right];

otherwise, it should be in the range of [left, mid-1].

One sentence summary: binary search for a "u" shape sorted array.

See the code below:

class Solution {
public:
    int findBestValue(vector<int>& arr, int target) {
        long a = -1e9, b = 1e9;
        return help(arr, a, b, target);
    }

private:
    int cal(int a, vector<int>& arr, int tar) {
        long sum = 0;
        for(auto &c : arr) {
            if(c<=a) sum += c;
            else sum += a;
        }
        return abs(sum - tar);
    }

    int help(vector<int>& arr, long left, long right, int tar) {
        if(left == right) return left; //base case
        if(left + 1 == right) {//base case due to boundary
            return cal(left, arr, tar) <= cal(right, arr, tar) ? left : right;
        }
        long mid = left + (right - left)/2;
        long x = cal(mid, arr, tar), y = cal(mid-1, arr, tar);
        if(y<=x) return help(arr, left, mid, tar);
        return help(arr, mid, right, tar);
    }
};

Leetcode 1283: Find the Smallest Divisor Given a Threshold

https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/description/

Notes:

This question is designed for a binary search!

In general, when can we apply a binary search?  If the target satisfies the following conditions,

1): the target is in a finite range;

2): when the target is <= threshold values, it always true or false;

then we can use a binary search.

For this question, the initial left can be set as 1, and the right can set as 10^6  + 1(why? please think for a while if cannot get it), which represents the range of [left, right).

Then we can check whether the mid = left + (right - left) /2, is the right divider or not.

If it can give a result which is larger than the threshold, it means it is too small and we need to go the range of [mid + 1,   right);

otherwise, we need to go to the range of [left, mid).

See the code below:

class Solution {
public:
    int smallestDivisor(vector<int>& nums, int threshold) {
        int left = 1, right = 1e6 + 1;
        while(left < right) {
            int mid = left + (right - left)/2;
            int ct = 0;
            for(auto &a : nums) {
                ct += a/mid;
                if(a%mid > 0) ++ct;
            }
            if(ct > threshold) left = mid + 1;
            else right = mid;
        }
        return left;
    }
};

Lintcode 848: Minimize Max Distance to Gas Station

https://www.lintcode.com/problem/minimize-max-distance-to-gas-station/description

On a horizontal number line, we have gas stations at positions stations[0], stations[1], ..., stations[N-1], where N = stations.length.

Now, we add K more gas stations so that D, the maximum distance between adjacent gas stations, is minimized.

Return the smallest possible value of D.

Example

Example 1:

Input：stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，K = 9
Output：0.50
Explanation：The distance between adjacent gas stations is 0.50

Example 2:

Input：stations = [3,6,12,19,33,44,67,72,89,95]，K = 2
Output：14.00
Explanation：construction of gas stations at 86 locations

Notice

1.stations.length will be an integer in range [10, 2000].
2.stations[i] will be an integer in range [0, 10^8].
3.K will be an integer in range [1, 10^6].
4.Answers within 10^-6 of the true value will be accepted as correct.

Notes:

This question can be solved by the binary search method.

Apparently, the question is asking for a min of maximum. Let say minMax, when val >= minMax, we can always finish one event; otherwise, it cannot be done. And val is apparently in a range.

So it is a binary search!

See the code below:

class Solution {
public:
    /**
     * @param stations: an integer array
     * @param k: an integer
     * @return: the smallest possible value of D
     */
    double minmaxGasDist(vector<int> &stations, int k) {
        // Write your code here
        sort(stations.begin(), stations.end());
        double epslon = 0.00001, left = epslon, right = stations.back();
        while(left + epslon < right) {
            double mid = left + (right - left) / 2;
            if(!isValid(stations, k, mid)) left = mid;
            else right = mid;
        }
        return left;
    }

private:
    bool isValid(vector<int>& gs, int k, double mid) {
        int ct = 0;
        double sum = 0;
        for(int i=0; i+1<gs.size(); ++i) {
            double dis = (double) (gs[i+1] - gs[i]);
            ct += (int)(dis/mid);
        }
        return ct <= k;
    }
};

Leetcode 1234: Replace the Substring for Balanced String

https://leetcode.com/contest/weekly-contest-159/problems/replace-the-substring-for-balanced-string/

You are given a string containing only 4 kinds of characters 'Q', 'W', 'E' and 'R'.

A string is said to be balanced if each of its characters appears n/4 times where n is the length of the string.

Return the minimum length of the substring that can be replaced with any other string of the same length to make the original string s balanced.

Return 0 if the string is already balanced.

Example 1:

Input: s = "QWER"
Output: 0
Explanation: s is already balanced.

Example 2:

Input: s = "QQWE"
Output: 1
Explanation: We need to replace a 'Q' to 'R', so that "RQWE" (or "QRWE") is balanced.

Example 3:

Input: s = "QQQW"
Output: 2
Explanation: We can replace the first "QQ" to "ER". 

Example 4:

Input: s = "QQQQ"
Output: 3
Explanation: We can replace the last 3 'Q' to make s = "QWER".

Constraints:

• 1 <= s.length <= 10^5
• s.length is a multiple of 4
• s contains only 'Q', 'W', 'E' and 'R'.

Notes:

This question can be solved by the sliding window method.

Since we can change the chars in the substring by any other chars, the counting of the rest chars outside the substring can always be increased or no change.

Thus, if it can be modified to be a balanced string, for each kind of char, the counting outside the substring need to be no larger than len / 4.

Then a sliding window can solve it.

See the code below:

class Solution {
public:
    int balancedString(string s) {
        int len = s.size(), res = len;
        unordered_map<char, int> mp;
        for(auto &a : s) ++mp[a];//counts ouside the windwo
        for(int i=0, j=0; j<len; ++j) {
            --mp[s[j]];//in the window
            while(i<len && mp['Q'] <= len/4 && mp['W'] <= len/4 && mp['E'] <= len/4 && mp['R'] <= len/4) {
                res = min(res, j - i + 1);
                ++mp[s[i++]];
            }
        }
        return res;
    }
};

A binary search method can also solve this problem. The min = 0, the max = length. Then the question become to find whether there is substring of length = mid = min + (max - min) / 2 existed, which can leave the remaining strings with the counts of each char no larger than len / 4.

Leetcode 778: Swim in Rising Water

https://leetcode.com/problems/swim-in-rising-water/description/

On an N x N grid, each square grid[i][j] represents the elevation at that point (i,j).

Now rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distance in zero time. Of course, you must stay within the boundaries of the grid during your swim.

You start at the top left square (0, 0). What is the least time until you can reach the bottom right square (N-1, N-1)?

Example 1:

Input: [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.

You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

Example 2:

Input: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Explanation:
 0  1  2  3  4
24 23 22 21  5
12 13 14 15 16
11 17 18 19 20
10  9  8  7  6

The final route is marked in bold.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

Note:

1. 2 <= N <= 50.
2. grid[i][j] is a permutation of [0, ..., N*N - 1].

Notes:

This question basically asks for the minimum of the maximum of any path from the source to the end.

So binary search + bfs (or dsf) can solve this problem.

The basic idea is that: the minimum must be inside a range. When it is above some value, we can always visit the end from the source; otherwise, we cannot. So binary search will work.

For each proposed value, we just run a bfs, to see whether we can visit the end or not. If not, we need to increase the left boundary; otherwise, decrease the right boundary.

See the code below:

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid.front().size(), left = 0, right = m*n;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(!canFinish(mid, grid)) left = mid + 1;
            else right = mid;
        }
        return left;
    }

private:
    bool canFinish(int mid, vector<vector<int>>& grid) {
        if(grid[0][0] > mid) return false;
        int m = grid.size(), n = grid.front().size();
        if(grid[m-1][n-1] > mid) return false;
        vector<vector<int>> visit(m, vector<int>(n, 0));
        queue<pair<int, int>> q;
        q.push({0, 0});
        visit[0][0] = 1;
        vector<int> dirs = {-1, 0, 1, 0, -1};
        while(q.size()) {
            auto t = q.front();
            q.pop();
            for(int i=0; i+1 < dirs.size(); ++i) {
                int x = t.first + dirs[i], y = t.second + dirs[i+1];
                if(x<0 || x>=m || y<0 || y>=n || visit[x][y] || grid[x][y] > mid) continue;
                if(x == m-1 && y == n-1) return true;
                visit[x][y] = 1;
                q.push({x, y});
            }
        }
        return false;
    }
};

Online OA1: Minimum Strongly Connected Network

Q: Minimum Strongly Connected Network

A group of software engineers want to develop an algorithm for finding strongly connected groups among members of a social networking site. A group of people are considered to be strongly connected if each person knows each other person within the group.

Given M nodes and N edges develop an algorithm that determines the minimum size of the largest strongly connected group.

Constraints:
1 <= N <= 100000
0 <= M <= 10000
0 <= M <= N*(N-1)/2


Notes:

This question seems one of the popular OA questions . In this link below,

http://canyon289.github.io/MinStrongNetwork.html#click-to-start-search

you can find a complete description of this question, plus some examples and ideas (but it seems that the idea on this page is not a good one to solve this problem.)

Let us begin with some small cases:

when N = 1, it always is 1;

when N = 2, it is 1 when M <1, and it is 2 when M>=1;

when N = 3, it is 1 when M<1, and it is 2 when M>=1 and M<3, and it is 3 when M>=3;

when N = 4, it is 1 when M<1, and it is 2 when (which is the key part), ... and it is 4 when M>=6;


Now let us focus on the key part:

when N = 4, if we link the 4 nodes into a circle with 4 edges (M=4), then it is still 2. If we add another edge (M=5), then it becomes 3; then add another one (M=6), they are fully connected.

Thus,
when N = 4, it is 1 when M<1, and it is 2 when M>=1 and M<=4, and it is 3 when M=5, and it is 4 when M>= 6.

So it seems that one way to solve this problem is that we just need to form a circle first, and then add more edges with the constrain that do not increase the size of any strongly connected components (scc) until have to. And this is essentially the idea in that link cited above. But it seems have some problems. Firstly, is this idea correct?

Let us look at the case when N = 5.

If we follow the idea in the link, we form a circle with 5 nodes which gives us 5 edges. Now we cannot add one more edge since it will always make the minimum size of the largest scc (lscc) to become 3.

However, if we form a circle with 4 nodes first which gives 4 edges, and we have last node unconnected. In order to better illustrate the idea, let us label the node from 1 to 5, and 1 to 4 are connected forming a circle consecutively. So we then can connect the 5th node with 1 and 3 forming another 2 edges without increase the minimum size of the lscc. (or connect 2 and 4 nodes, which gives the same results.)

But now we can have 6 edges with 5 nodes with the minimum size of lscc of 2!!!

So the above greedy way does not work.

Now let's try something different:

The answer to this question apparently is in a range: the min = 1, and the max = N. And it is asking for the minimum size of the lscc, so it can naturally lead the very fundamental binary search idea.

Now let's set Left = 1, Right = N, then Mid = Left + (Right - Left)/2. If we cannot connect the N nodes in such a way that the minimum size of the lscc is not larger than Mid with M edges, or there are more edges than needed and we have to increase Mid in order to run up all the M edges, then current Mid is too small (or invalid), and we can update Left = Mid + 1; otherwise, we can update Right = Mid.

In this way, we can eventually find the correct value which is Left == Right.

So now the key question becomes: given N nodes and the lscc is Mid, what is the maximum number of edges that can be added onto? And we need the answer to this question in the above binary searching.

Again let's start with small cases:

when  N = 4, and Mid  = 2. We firstly fully connect 1 to 2, and 3 to 4, to form two scc with a size of Mid = 2. Now we have 2 edges. Next, we can connect 1 to 3, and 2 to 4. (or 1 to 4, and 2 to 3). So the maximum is 4 edges;

when N = 4, and Mid = 3. We can firstly fully connect 1, 2, 3 to form a scc with a size of 3, then connect 4 to 1, and 4 to 2. (or 4 to 1, and 4 to 3; or 4 to 2, and 4 to 3). So one of the key observation is that 4 cannot connect all the nodes in a scc, otherwise it will increase the size of scc by 1. So the maximum is 5 edges.

It seem still not enough to derive the result that can be applied to all the cases. Let us continue,

when N = 5, and Mid = 2. Follow the similar idea of when N = 4, we can firstly form 2 scc's by fully connect 1 to 2, and 3 to 4, respectively. Next, we can connect 1 to 3 and 2 to 4. The last step is new: we have a unconnected node 5. After some trails and errors, it is found that we can connect 5 to 1, and 5 to 3. (or 5 to 1, and 5 to 4, or 5 to 2, and 5 to 3, or 5 to 2, and 5 to 4. The key is the same, 5 cannot connect all the nodes in a scc). So the maximum is 6 edges.

It is time to make some summaries:

1): we form as many scc's as possible with a size of Mid; the total number of the scc edges is easy to calculate

2): we need to calculate all the possible connections between every two scc's with a size of Mid;

3): we need to take care of the remainders whose size is smaller than Mid (it turns out later that this is essentially the same as 2)).

We need to figure out how many edges we can place between nodes.

For 1): the answer is straightforward: (N/Mid) * (Mid*(Mid-1)/2) = num_scc *  edge_num_scc;

Step 2) seems not that easy. Let start again with some example, when N = 6, and Mid = 3. So we have 2 scc's with a size of 3. Let say 1, 2, 3 are in a scc, and 4, 5, 6 in the other scc. Now we can connect 1 to 4 and 5 (2 more edges) but not 6 (or it will increase the size of scc); then 2 to 5 and 6, then 3 to 6 and 4. The total maximum connections between 2 scc's with the same size of Mid is Mid * (Mid - 1).

But we may have more than 2 scc's. For example, when N = 9 and Mid = 3. In this case, every 2 scc's can be connected in the similar way, which gives a factor of  F = (N/Mid)*(N/Mid - 1)/2. Thus, the total maximum number of edges for step 2 is: F * Mid * (Mid - 1) = (N/Mid)*(N/Mid - 1)/2 * Mid * (Mid - 1).

Before we move on to step 3), let look an interesting question first. What are the maximum number of connections between 2 scc's with different sizes, without increasing the minimum size of lscc?

Let say one scc has a size of Mid, and the other is R which is smaller than Mid. Similar to the above case of 2 scc's with the same size, every node in the second scc can connect (Mid - 1) nodes in the first one. Thus, the total number of edges is R * (Mid - 1).

If there are (N/Mid)  scc's, then the total number of edges is (N/Mid) * R * (Mid - 1), which is one part of the answer to the step 3).

What is still missing?

If we have more than 1 node in the remaining. For example, Mid = 4, R = 3. The 3 nodes can form a scc first. So this part will give R* (R - 1)/2 edges.

Thus the final answer to step 3) is R* (R - 1)/2 + (N/Mid) * R * (Mid - 1).

The total number of edges are the sum the all three steps.

We are done. And the next step is coding.


Please see the code below:

#include <iostream>
#include <vector>

using namespace std;

int minMax_scg(int &m, int &n);
int maxEdge(int &m, int &max_scg);

int main() {
    int num_node = 100, num_edge = 4900;
    return minMax_scg(num_node, num_edge);
}

int minMax_scg(int &m, int &n) {
    int left = 1, right = m;
    while(left < right) {
        int mid = left + (right - left) / 2;
        if(maxEdge(m, mid) < n) left = mid + 1;
        else right = mid;
    }
    cout<<"The minimum size of the largest scc = " <<left<<endl;
    return left;
}

int maxEdge(int &m, int &max_scg) {
    int num_scg_compo = m / max_scg;
    int remainer = m % max_scg;
    int a = max_scg, b = num_scg_compo, c = remainer;
    int maxE = b*a*(a-1)/2 + b*(b-1)/2*a*(a-1) + c*(c-1)/2 + b*c*(a-1);
    cout<<"num_node = "<<m<<" max_scg = "<<max_scg<<" maxNumEdge = "<<maxE<<endl;
    return maxE;
} 

Please leave any comment if you find some incorrect places or improvements. Any discussion is also welcome! 

PS: after finishing the writing, I feel that the there may be existed formula to calculate the maximum number of edges for a un-directed graph with N nodes and the lscc of K (K <= N). Please let me know if you find this somewhere. Thanks.

Leetcode 792: Number of Matching Subsequences

https://leetcode.com/problems/number-of-matching-subsequences/description/

Notes:

This question is the same as the follow up question of Leetcode 392.

See the code below:

class Solution {
public:
    int numMatchingSubseq(string S, vector<string>& words) {
        int res = 0;
        vector<vector<int>> ids(26);
        for(int i=0; i<S.size(); ++i) ids[S[i]-'a'].push_back(i);
        for(auto &w : words) {
            if(w.size() > S.size()) continue;
            int id = -1, i = 0;
            for(; i<w.size(); ++i) {
                int t = w[i] - 'a';
                auto it = upper_bound(ids[t].begin(), ids[t].end(), id);
                if(it == ids[t].end()) break;
                id = *it;
            }
            if(i == w.size()) ++res;
        }
        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 981: Time Based Key-Value Store

https://leetcode.com/problems/time-based-key-value-store/description/



Notes:

This question is pretty straightforward, and it is essentially a question of data structure + binary search. See the code below,

class TimeMap {
public:
    /** Initialize your data structure here. */
    TimeMap() {

    }

    void set(string key, string value, int timestamp) {
        if(ump.count(key) == 0) ump[key].push_back({timestamp, value});
        auto it = upper_bound(ump[key].begin(), ump[key].end(), pair<int, string>(timestamp, ""));
        ump[key].insert(it, {timestamp, value});
    }

    string get(string key, int timestamp) {
        if(ump.count(key) == 0) return "";
        auto it = upper_bound(ump[key].begin(), ump[key].end(), pair<int, string>(timestamp, ""));
        if(it != ump[key].end() && it->first == timestamp) return it->second;
        if(it == ump[key].begin()) return "";
        return (it-1)->second;
    }
private:
    unordered_map<string, vector<pair<int, string>>> ump;
};

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap* obj = new TimeMap();
 * obj->set(key,value,timestamp);
 * string param_2 = obj->get(key,timestamp);
 */

It should be noticed that inside the upper_bound(), the type of pair has to be written explicitly as pair<int, string>, otherwise compiler error will occur.

Another way using a different structure. Pay attention to the property of map.upper_bound().

int _=[](){//increase run spead
 ios::sync_with_stdio(false);
 cin.tie(nullptr);
 return 0;
 }();

class TimeMap {
public:
    /** Initialize your data structure here. */
    TimeMap() {
       
    }
   
    void set(string key, string value, int timestamp) {
        ump[key][timestamp] = value;
    }

    string get(string key, int timestamp) {
        if(ump.count(key) == 0) return "";
        auto it = ump[key].upper_bound(timestamp); //find the upper bound of the key of the map...
        if(it == ump[key].begin()) return "";
        return (--it)->second;
    }

private:
    unordered_map<string, map<int, string>> ump;
};

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap* obj = new TimeMap();
 * obj->set(key,value,timestamp);
 * string param_2 = obj->get(key,timestamp);
 */