# [C++] Clean Code - 7 lines with Explanation

• ``````class Solution {
public:
vector<string> findRestaurant(vector<string>& l1, vector<string>& l2) {
int noshow = l1.size() + l2.size();  // use sum of size as a punishment for missing in either list;
map<string, int> punish;
for (int i = 0; i < l1.size(); i++) punish[l1[i]] = i - noshow; // unpunish 1 * noshow for showing up at least in l1
for (int j = 0; j < l2.size(); j++) punish[l2[j]] += j - noshow;// unpunish 1 * noshow for showing up at least in l2
map<int, vector<string>> rank;
for (auto p : punish) rank[p.second].push_back(p.first);
return rank.begin()->second;
}
};
``````

The idea is to use `sum of index` in both list as `score` for every restaurant ever appeared, but need to manage `punishment` for not show up in either list.

1. Use `sum of size as a punishment` for missing in either list : `l1.size() + l2.size()`, the punish need to be big enough to bigger than showing up at the end of both list;
2. Create a map, for every restaurant appear in either list, initialize the score as `2 times punish`;
3. For every restaurant in every list, remove `1*punish` for showing up in 1 list.
4. On top of the punishment, don't forget to add `index`s as score, the smaller the better.

Intuitively

``````class Solution {
public:
vector<string> findRestaurant(vector<string>& l1, vector<string>& l2) {
int punish = l1.size() + l2.size(); // use sum of size as a punishment for missing in either list;
map<string, int> m;
for (int i = 0; i < l1.size(); i++) {
m.emplace(l1[i], punish * 2);   // add 2 times punish by default
m[l1[i]] += i - punish;         // reduce 1 punish for appearing in l1
}
for (int j = 0; j < l2.size(); j++) {
m.emplace(l2[j], punish * 2);   // add 2 times punish by default
m[l2[j]] += j - punish;         // reduce 1 punish for appearing in l2
}

map<int, vector<string>> rank; // use a sorted map rank the restaurants
for (auto p : m) {
rank[p.second].push_back(p.first);
}
return rank.begin()->second;
}
};
``````

Simplified
In the above solution, we really wish we have a type with default value as `2*punishment` in the map.

• Unfortunately map`[]` operator will create an value default to `0`;
• Fortunately we don't really need to initialize the score as `2 times punishment`;
• The score can be negative, but still, the smaller the better:
``````class Solution {
public:
vector<string> findRestaurant(vector<string>& l1, vector<string>& l2) {
int punish = l1.size() + l2.size();  // use n as a punishment for missing in either list;
map<string, int> m;
for (int i = 0; i < l1.size(); i++) m[l1[i]] += i - punish;
for (int j = 0; j < l2.size(); j++) m[l2[j]] += j - punish;
map<int, vector<string>> rank;
for (auto p : m) rank[p.second].push_back(p.first);
return rank.begin()->second;
}
};
``````

Yet Another Solution

``````class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
int n = list1.size() + list2.size();
map<string, vector<int>> m;
for (int i = 0; i < list1.size(); i++) {
m[list1[i]] = {i, n};
}
for (int j = 0; j < list2.size(); j++) {
if (m.count(list2[j])) {
m[list2[j]][1] = j;
}
else {
m[list2[j]] = {n, j};
}
}

int minsum = INT_MAX;
map<int, vector<string>> sumMap;
for (auto p : m) {
int sum = p.second[0] + p.second[1];
sumMap[sum].push_back(p.first);
minsum = min(minsum, sum);
}

return sumMap[minsum];
}
};
``````

• @alexander Hey I'm new to STL,can you please explain me how does this work?
rank[p.second].push_back(p.first);
Sorry for the naïve question.Hope you'll help! :)

• @mansipradhan rank is defined as: `map<int, vector<string>> rank`

``````        map<int, vector<string>> rank; // use a sorted map rank the restaurants
for (auto p : m) {
rank[p.second].push_back(p.first);
}
``````

`std::map::[key]` is an overloaded operator act just the same as `java.util.Map.get(key)`, retrieve the `value` for the given `key`.
The `[]` will create an default value if the key is not found, in this case `rank[p.second]` will create an empty vector if `p.second` is not found as a `key` in the map `rank`.

equals:

``````        map<int, vector<string>> rank; // use a sorted map rank the restaurants
for (pair<string, int> p : m) {
string restaurant = p.first;
int punish = p.second;
vector<string> restarauts = rank[punish];
restarauts.push_back(restaurant);
}
``````

Please refer to this for more information:
http://www.cplusplus.com/reference/map/map/operator[]/

• @alexander Got it.
Thanks :)

• This post is deleted!

• My C++ code, straightforward using find(), and I get 122ms. Not very fast, but easy to understand. :)

``````class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
vector<string> result;
unordered_multimap<int, string> mp;
int min_sum = INT_MAX;
for (int i = 0; i < list1.size(); i++) {
if (find(list2.begin(), list2.end(), list1[i]) != list2.end()) {
int temp = find(list2.begin(), list2.end(), list1[i]) - list2.begin() + i;
if (temp <= min_sum) {
mp.insert(pair<int, string>(temp, list1[i]));
min_sum = temp;
}
}
}
unordered_multimap<int, string>::iterator it;
for (it = mp.begin(); it != mp.end(); it++) {
if (it->first == min_sum)
result.push_back((*it).second);
}
return result;
}
};

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.