# 1772. Sort Features by Popularity

• Time: $O(\texttt{sort}(\texttt{features}) + \Sigma |\texttt{responses[i]}|)$
• Space: $O(|\texttt{features}| + |\texttt{responses}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public: vector sortFeatures(vector& features, vector& responses) { vector ans; vector> featCount; // {i: count[features[i]]} unordered_map count; for (const string& res : responses) { istringstream iss(res); unordered_set seen; for (string token; getline(iss, token, ' ');) seen.insert(token); for (const string& token : seen) ++count[token]; } for (int i = 0; i < features.size(); ++i) featCount.emplace_back(i, count[features[i]]); ranges::sort(featCount, [](const auto& a, const auto& b) { return a.second == b.second ? a.first < b.first : a.second > b.second; }); for (const auto& [i, count] : featCount) ans.push_back(features[i]); return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public String[] sortFeatures(String[] features, String[] responses) { String[] ans = new String[features.length]; int[][] featCount = new int[features.length][]; // {i: count[features[i]]} Map count = new HashMap<>(); for (final String res : responses) for (final String token : new HashSet<>(Arrays.asList(res.split(" ")))) count.merge(token, 1, Integer::sum); for (int i = 0; i < features.length; ++i) featCount[i] = new int[] {i, count.getOrDefault(features[i], 0)}; Arrays.sort(featCount, (a, b) -> a[1] == b[1] ? a[0] - b[0] : b[1] - a[1]); for (int i = 0; i < features.length; ++i) ans[i] = features[featCount[i][0]]; return ans; } }