Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1772. Sort Features by Popularity - Leetcode Solution

Code Implementation

from collections import Counter

class Solution:
    def sortFeatures(self, features, responses):
        # Count the number of responses each feature appears in
        feature_count = Counter()
        for response in responses:
            seen = set()
            for word in response:
                if word in features:
                    seen.add(word)
            for word in seen:
                feature_count[word] += 1

        # Sort features by count (descending), then by their order in original features
        feature_index = {feature: i for i, feature in enumerate(features)}
        features_sorted = sorted(features, key=lambda f: (-feature_count[f], feature_index[f]))
        return features_sorted
      
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<string> sortFeatures(vector<string>& features, vector<vector<string>>& responses) {
        unordered_map<string, int> count;
        for (auto& response : responses) {
            unordered_set<string> seen;
            for (auto& word : response) {
                if (find(features.begin(), features.end(), word) != features.end())
                    seen.insert(word);
            }
            for (auto& word : seen) count[word]++;
        }
        unordered_map<string, int> featureIndex;
        for (int i = 0; i < features.size(); ++i) featureIndex[features[i]] = i;

        sort(features.begin(), features.end(), [&](const string& a, const string& b) {
            if (count[a] != count[b]) return count[a] > count[b];
            return featureIndex[a] < featureIndex[b];
        });

        return features;
    }
};
      
import java.util.*;

class Solution {
    public List<String> sortFeatures(List<String> features, List<List<String>> responses) {
        Map<String, Integer> count = new HashMap<>();
        for (List<String> response : responses) {
            Set<String> seen = new HashSet<>();
            for (String word : response) {
                if (features.contains(word)) seen.add(word);
            }
            for (String word : seen) count.put(word, count.getOrDefault(word, 0) + 1);
        }
        Map<String, Integer> featureIndex = new HashMap<>();
        for (int i = 0; i < features.size(); ++i) featureIndex.put(features.get(i), i);

        features.sort((a, b) -> {
            int cmp = Integer.compare(count.getOrDefault(b, 0), count.getOrDefault(a, 0));
            if (cmp != 0) return cmp;
            return Integer.compare(featureIndex.get(a), featureIndex.get(b));
        });
        return features;
    }
}
      
var sortFeatures = function(features, responses) {
    const count = {};
    for (const response of responses) {
        const seen = new Set();
        for (const word of response) {
            if (features.includes(word)) seen.add(word);
        }
        for (const word of seen) {
            count[word] = (count[word] || 0) + 1;
        }
    }
    const featureIndex = {};
    for (let i = 0; i < features.length; ++i) {
        featureIndex[features[i]] = i;
    }
    features.sort((a, b) => {
        if ((count[b] || 0) !== (count[a] || 0)) return (count[b] || 0) - (count[a] || 0);
        return featureIndex[a] - featureIndex[b];
    });
    return features;
};

Problem Description

Given a list of features (strings) and a list of responses (each response is a list of strings), your task is to sort the features in descending order of popularity. A feature's popularity is defined as the number of responses in which it appears at least once. If two features have the same popularity, maintain their original order from the input features list.

Constraints:
  • Each feature is a unique string.
  • Each response may mention a feature multiple times, but only count once per response.
  • All features in features should be present in the output, sorted as described.
  • There is only one valid solution for the output order.

Thought Process

The goal is to determine how frequently each feature is mentioned across all responses, counting each response only once per feature. At first, one might think of counting every occurrence, but the key is to count the number of responses each feature appears in, ignoring duplicate mentions in the same response.

A brute-force approach would be to check, for each feature, every response to see if the feature appears, and tally up the counts. However, this could be slow for large inputs.

To optimize, we can process each response once, collecting which features are mentioned in that response (using a set to avoid duplicates), then increment the count for each feature found. Finally, we sort the features by their counts (descending), breaking ties by their original order.

Solution Approach

To solve the problem efficiently, follow these steps:
  1. Initialize a Counter: Use a hash map (dictionary) to keep track of how many responses each feature appears in.
  2. Process Each Response: For every response:
    • Create a set to store unique features mentioned in this response.
    • Iterate through the words in the response. If a word is a feature, add it to the set.
    • After processing the response, increment the count for each feature in the set.
  3. Track Original Order: Store the original index of each feature so you can break ties later.
  4. Sort Features: Sort the features list using a custom sorting key:
    • Primary: Negative of the count (so higher counts come first).
    • Secondary: Original index (so earlier features come first in case of a tie).
  5. Return the Sorted List: Output the features in the new order.
This approach ensures that each response is only processed once, and each feature's popularity is counted efficiently.

Example Walkthrough

Input:
features = ["battery", "screen", "camera", "design"]
responses = [["battery", "camera", "battery"], ["screen", "design"], ["camera", "battery"], ["design", "screen", "screen"]]

Step-by-step process:
  1. For the first response ["battery", "camera", "battery"]:
    Unique features: {"battery", "camera"}
    Increment count for "battery" and "camera".
  2. Second response ["screen", "design"]:
    Unique features: {"screen", "design"}
    Increment count for "screen" and "design".
  3. Third response ["camera", "battery"]:
    Unique features: {"camera", "battery"}
    Increment count for "camera" and "battery".
  4. Fourth response ["design", "screen", "screen"]:
    Unique features: {"design", "screen"}
    Increment count for "design" and "screen".
Final counts:
  • "battery": 2
  • "screen": 2
  • "camera": 2
  • "design": 2
Since all have the same count, the original order is preserved:
["battery", "screen", "camera", "design"]

Time and Space Complexity

Brute-force approach:
  • For each feature, check every response: O(F * R * L), where F = number of features, R = number of responses, L = average response length.
Optimized approach:
  • Processing all responses: O(R * L), since each response is scanned once.
  • Updating counts: O(F), since each feature is updated at most once per response.
  • Sorting features: O(F log F).
  • Total time: O(R * L + F log F).
  • Space: O(F) for the counts and original indices.
This is efficient for large inputs.

Summary

The solution efficiently counts how many responses each feature appears in by processing each response once and using a set to avoid duplicate counting within the same response. Sorting the features by popularity, with a stable tie-breaker using the original order, yields the correct result. This approach is both intuitive and optimal, making good use of hash maps and sorting to solve the problem elegantly.