Watch 2 video solutions for Sort Features by Popularity, a medium level problem involving Array, Hash Table, String. This walkthrough by Fisher Coder has 1,020 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string array features where features[i] is a single word that represents the name of a feature of the latest product you are working on. You have made a survey where users have reported which features they like. You are given a string array responses, where each responses[i] is a string containing space-separated words.
The popularity of a feature is the number of responses[i] that contain the feature. You want to sort the features in non-increasing order by their popularity. If two features have the same popularity, order them by their original index in features. Notice that one response could contain the same feature multiple times; this feature is only counted once in its popularity.
Return the features in sorted order.
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 <= 1041 <= features[i].length <= 10features contains no duplicates.features[i] consists of lowercase letters.1 <= responses.length <= 1021 <= responses[i].length <= 103responses[i] consists of lowercase letters and spaces.responses[i] contains no two consecutive spaces.responses[i] has no leading or trailing spaces.Problem Overview: You receive a list of product features and a list of user responses. Each response is a sentence describing which features users liked. The task is to rank the features by how many responses mention them. If two features have the same popularity, keep their original order from the input list.
Approach 1: Direct Counting with Nested Scans (Brute Force) (Time: O(F * R * W), Space: O(1))
The straightforward idea checks each feature against every response. For each feature, iterate through all responses and search the response string to see whether the feature appears. To avoid counting duplicates inside a single response, maintain a temporary check to ensure the feature is counted only once per response. This method repeatedly scans strings and quickly becomes expensive when the number of features or responses grows. It works for small inputs but performs poorly because every feature triggers another full scan of all responses.
Approach 2: Hash Table + Custom Sorting (Time: O(R * W + F log F), Space: O(F))
The efficient strategy processes responses only once. Use a hash table to store the popularity count for each feature. For every response, split it into words using basic string processing. Convert the words into a set so a feature mentioned multiple times in the same response is counted once. Then iterate through the set and increment the corresponding feature counter if the word matches a feature.
After counting, sort the original feature list using custom sorting. The comparator sorts by descending popularity count and uses the original index as a tiebreaker to preserve input order. Because only the feature list is sorted, the expensive response processing happens just once. This keeps the runtime efficient even with large datasets.
The key insight is separating counting from ranking. Hash table lookups give O(1) updates while sorting handles the final ordering constraint. The algorithm scales well because the heavy work—processing responses—runs linearly.
Recommended for interviews: Interviewers expect the hash table + custom sorting approach. It demonstrates awareness of duplicate handling, efficient counting, and stable ordering using original indices. Mentioning the brute force approach first shows you understand the naive baseline, but implementing the hash-based counting solution shows practical problem-solving skill.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Counting with Nested Scans | O(F * R * W) | O(1) | Useful for understanding the baseline logic when constraints are very small |
| Hash Table + Custom Sorting | O(R * W + F log F) | O(F) | General case. Efficient counting with hash lookups and sorting by popularity |