Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1772.html

1772. Sort Features by Popularity

Level

Medium

Description

You are given a string array features where features[i] is a single word representing the name of a feature of the latest product you are working on. You made a survey where users reported which features they like. You are given a string array responses, where responses[i] is a string containing space-separated words.

You want to sort the features according to their popularity. More formally, let appearances(word) be the number of is such that responses[i] contains word as a word. Then the x-th feature is more popular than the y-th feature if appearances(features[x]) > appearances(features[y]).

Return an array sortedFeatures consisting of the feature names sorted by their popularity. If the x-th and y-th features have the same popularity where x < y, then you should put the x-th feature before the y-th one.

Example 1:

Input: features = [“cooler”,”lock”,”touch”], responses = [“i like cooler cooler”,”lock touch cool”,”locker like touch”]

Output: [“touch”,”cooler”,”lock”]

Explanation: appearances(“cooler”) = 1, appearances(“lock”) = 1, appearances(“touch”) = 2. Since “cooler” and “lock” both had 1 appearance, “cooler” comes first because “cooler” came first in the features array.

Example 2:

Input: features = [“a”,”aa”,”b”,”c”], responses = [“a”,”a aa”,”a a a a a”,”b a”]

Output: [“a”,”aa”,”b”,”c”]

Constraints:

  • 1 <= features.length <= 10^4
  • 1 <= features[i].length <= 10
  • features contains no duplicates.
  • features[i] consists of lowercase letters.
  • 1 <= responses.length <= 10^2
  • 1 <= responses[i].length <= 10^3
  • responses[i] consists of lowercase letters and spaces.
  • responses[i] contains no two consecutive spaces.
  • responses[i] has no leading or trailing spaces.

Solution

Use two maps to store the indices of each feature in features, and the appearances of each feature in responses. Loop over features and responses to put the value into the two maps. Then sort features first according to the appearances in descending order next according to the indices in ascending order. Return the sorted array features.

  • class Solution {
    public String[] sortFeatures(String[] features, String[] responses) {
        Map<String, Integer> indicesMap = new HashMap<String, Integer>();
        int featuresCount = features.length;
        for (int i = 0; i < featuresCount; i++)
            indicesMap.put(features[i], i);
        Map<String, Integer> appearancesMap = new HashMap<String, Integer>();
        int length = responses.length;
        for (int i = 0; i < length; i++) {
            String response = responses[i];
            String[] array = response.split(" ");
            Set<String> set = new HashSet<String>();
            for (String word : array)
                set.add(word);
            for (String feature : features) {
                if (set.contains(feature)) {
                    int count = appearancesMap.getOrDefault(feature, 0) + 1;
                    appearancesMap.put(feature, count);
                }
            }
        }
        Arrays.sort(features, new Comparator<String>() {
            public int compare(String str1, String str2) {
                int appearances1 = appearancesMap.getOrDefault(str1, 0);
                int appearances2 = appearancesMap.getOrDefault(str2, 0);
                if (appearances1 != appearances2)
                    return appearances2 - appearances1;
                else
                    return indicesMap.get(str1) - indicesMap.get(str2);
            }
        });
        return features;
    }
}

############

class Solution {
    public String[] sortFeatures(String[] features, String[] responses) {
        Map<String, Integer> cnt = new HashMap<>();
        for (String r : responses) {
            Set<String> ws = new HashSet<>();
            for (String w : r.split(" ")) {
                ws.add(w);
            }
            for (String w : ws) {
                cnt.put(w, cnt.getOrDefault(w, 0) + 1);
            }
        }
        int n = features.length;
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; ++i) {
            idx[i] = i;
        }
        Arrays.sort(idx, (i, j) -> {
            int d = cnt.getOrDefault(features[j], 0) - cnt.getOrDefault(features[i], 0);
            return d == 0 ? i - j : d;
        });
        String[] ans = new String[n];
        for (int i = 0; i < n; ++i) {
            ans[i] = features[idx[i]];
        }
        return ans;
    }
}

  • // OJ: https://leetcode.com/problems/sort-features-by-popularity/
// Time: O(R + FlogF)
// Space: O(F)
class Solution {
public:
    vector<string> sortFeatures(vector<string>& F, vector<string>& R) {
        unordered_map<string, int> m, index;
        for (int i = 0; i < F.size(); ++i) index[F[i]] = i;
        for (auto &r : R) {
            stringstream ss(r);
            string word;
            unordered_set<string> seen;
            while (ss >> word) {
                if (index.count(word)) seen.insert(word);
            }
            for (auto &s : seen) m[s]++;
        }
        sort(begin(F), end(F), [&](auto &a, auto &b) { return m[a] != m[b] ? m[a] > m[b] : index[a] < index[b]; });
        return F;
    }
};

  • class Solution:
    def sortFeatures(self, features: List[str], responses: List[str]) -> List[str]:
        cnt = Counter()
        for r in responses:
            ws = set(r.split())
            for s in ws:
                cnt[s] += 1
        return sorted(features, key=lambda x: -cnt[x])



  • func sortFeatures(features []string, responses []string) []string {
	cnt := map[string]int{}
	for _, r := range responses {
		ws := map[string]bool{}
		for _, s := range strings.Split(r, " ") {
			ws[s] = true
		}
		for w := range ws {
			cnt[w]++
		}
	}
	n := len(features)
	idx := make([]int, n)
	for i := range idx {
		idx[i] = i
	}
	sort.Slice(idx, func(i, j int) bool {
		d := cnt[features[idx[i]]] - cnt[features[idx[j]]]
		return d > 0 || (d == 0 && idx[i] < idx[j])
	})
	ans := make([]string, n)
	for i := range ans {
		ans[i] = features[idx[i]]
	}
	return ans
}

  • function sortFeatures(features: string[], responses: string[]): string[] {
    const cnt: Map<string, number> = new Map();
    for (const s of responses) {
        const vis: Set<string> = new Set();
        for (const w of s.split(' ')) {
            if (vis.has(w)) {
                continue;
            }
            vis.add(w);
            cnt.set(w, (cnt.get(w) || 0) + 1);
        }
    }
    const n = features.length;
    const idx: number[] = Array.from({ length: n }, (_, i) => i);
    idx.sort((i, j) => {
        const x = cnt.get(features[i]) || 0;
        const y = cnt.get(features[j]) || 0;
        return x === y ? i - j : y - x;
    });
    return idx.map(i => features[i]);
}

All Problems

All Solutions