Skip to content

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
31
class Solution {
 public:
  vector<string> sortFeatures(vector<string>& features,
                              vector<string>& responses) {
    vector<string> ans;
    vector<pair<int, int>> featCount;  // {i: count[features[i]]}
    unordered_map<string, int> count;

    for (const string& res : responses) {
      istringstream iss(res);
      unordered_set<string> 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 pair<int, int>& a, const pair<int, int>& 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
22
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<String, Integer> 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] ? Integer.compare(a[0], b[0]) : Integer.compare(b[1], a[1]));

    for (int i = 0; i < features.length; ++i)
      ans[i] = features[featCount[i][0]];

    return ans;
  }
}