Problem Description

You're developing a product with multiple features and want to understand which features are most popular based on user feedback.

You have two inputs:

• features: An array of strings where each string represents a feature name
• responses: An array of strings where each string contains space-separated words representing a user's response

The goal is to sort the features based on their popularity, which is defined as the number of responses that mention the feature at least once.

Key rules for sorting:

1. Features should be sorted in descending order by popularity (most popular first)
2. If two features have the same popularity, maintain their original order from the features array
3. If a feature appears multiple times in a single response, it only counts as 1 toward that feature's popularity

For example, if:

• features = ["camera", "battery", "screen"]
• responses = ["I love the camera and camera quality", "battery life is great", "camera is amazing"]

Then:

• "camera" appears in 2 responses (popularity = 2)
• "battery" appears in 1 response (popularity = 1)
• "screen" appears in 0 responses (popularity = 0)

The output would be ["camera", "battery", "screen"] sorted by popularity.

The solution uses a Counter to track how many responses contain each feature. For each response, it converts the response to a set of words (eliminating duplicates within that response) and increments the count for each word. Finally, it sorts the features list using the negative count as the key to achieve descending order.

Intuition

The core challenge is counting how many responses mention each feature while ensuring duplicate mentions within the same response don't inflate the count.

The natural approach is to think about what we need to track:

1. For each feature, we need to know how many different responses mentioned it
2. We need to handle the duplicate word issue within each response

The key insight is that when processing each response, we should first convert it to a set of unique words. This immediately solves the duplicate problem - if "camera" appears 3 times in one response, the set will only contain it once.

Once we have unique words per response, we can simply count occurrences across all responses. A hash table (Counter in Python) is perfect for this - we iterate through each response, extract unique words, and increment the count for each word we see.

For the sorting step, we realize that Python's sorted() function maintains the original order when elements have equal sort keys (stable sort). This means if we sort the original features array by popularity, features with the same popularity will naturally maintain their original order.

The trick with using -cnt[w] as the sort key is elegant: since Python sorts in ascending order by default, negating the count gives us descending order. Features not in cnt have a count of 0, and -0 is still 0, so they'll appear at the end in their original order.

This approach is efficient because we only scan each response once, and the sorting is done on the typically small features array rather than on all words found in responses.

Learn more about Sorting patterns.

Solution Approach

The implementation follows a straightforward process using a hash table for counting and custom sorting for the final result.

Step 1: Initialize the Counter

cnt = Counter()

We create a Counter object (hash table) to track how many responses contain each word.

Step 2: Process Each Response

for s in responses:
    for w in set(s.split()):
        cnt[w] += 1

For each response string s:

• Split the response into individual words using s.split()
• Convert the list of words to a set() to remove duplicates within that response
• For each unique word w in the set, increment its count in the hash table

The use of set() is crucial here - it ensures that if a word appears multiple times in one response, it only contributes 1 to the popularity count.

Step 3: Sort Features by Popularity

return sorted(features, key=lambda w: -cnt[w])

Sort the original features array using a custom key function:

• The key function lambda w: -cnt[w] returns the negative count for each feature
• Using negative values sorts in descending order (most popular first)
• If a feature doesn't exist in cnt, cnt[w] returns 0, so -cnt[w] is 0
• Python's sorted() is stable, meaning features with equal popularity maintain their original relative order

Time Complexity: O(N * M + F * log F) where:

• N is the number of responses
• M is the average number of unique words per response
• F is the number of features

Space Complexity: O(W) where W is the total number of unique words across all responses

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach:

Input:

• features = ["storage", "battery", "display", "camera"]
• responses = ["love the storage and battery battery", "camera quality is good", "battery lasts long and storage is huge", "display is broken"]

Step 1: Initialize Counter We start with an empty counter: cnt = {}

Step 2: Process Each Response

Response 1: "love the storage and battery battery"

• Split into words: ["love", "the", "storage", "and", "battery", "battery"]
• Convert to set: {"love", "the", "storage", "and", "battery"} (duplicate "battery" removed)
• Update counter:
  • cnt = {"love": 1, "the": 1, "storage": 1, "and": 1, "battery": 1}

Response 2: "camera quality is good"

• Split into words: ["camera", "quality", "is", "good"]
• Convert to set: {"camera", "quality", "is", "good"}
• Update counter:
  • cnt = {"love": 1, "the": 1, "storage": 1, "and": 1, "battery": 1, "camera": 1, "quality": 1, "is": 1, "good": 1}

Response 3: "battery lasts long and storage is huge"

• Split into words: ["battery", "lasts", "long", "and", "storage", "is", "huge"]
• Convert to set: {"battery", "lasts", "long", "and", "storage", "is", "huge"}
• Update counter (incrementing existing entries):
  • cnt["battery"] becomes 2 (was 1)
  • cnt["storage"] becomes 2 (was 1)
  • cnt["and"] becomes 2 (was 1)
  • cnt["is"] becomes 2 (was 1)
  • New words get count 1
  • cnt = {"love": 1, "the": 1, "storage": 2, "and": 2, "battery": 2, "camera": 1, "quality": 1, "is": 2, "good": 1, "lasts": 1, "long": 1, "huge": 1}

Response 4: "display is broken"

• Split into words: ["display", "is", "broken"]
• Convert to set: {"display", "is", "broken"}
• Update counter:
  • cnt["display"] becomes 1 (new)
  • cnt["is"] becomes 3 (was 2)
  • cnt["broken"] becomes 1 (new)

Step 3: Sort Features by Popularity

Now we sort our original features array using the counts:

• "storage": cnt["storage"] = 2, sort key = -2
• "battery": cnt["battery"] = 2, sort key = -2
• "display": cnt["display"] = 1, sort key = -1
• "camera": cnt["camera"] = 1, sort key = -1

Sorting by these keys (in ascending order of negative counts = descending order of actual counts):

1. "storage" and "battery" both have sort key -2 (highest popularity)
2. Since they have equal popularity, they maintain original order: "storage" before "battery"
3. "display" and "camera" both have sort key -1 (lower popularity)
4. They also maintain original order: "display" before "camera"

Final Output: ["storage", "battery", "display", "camera"]

The features are now sorted by popularity (2, 2, 1, 1) while maintaining original order for ties.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * k + n * log n)

Where:

• m is the number of responses
• k is the average number of words per response
• n is the number of features

Breaking down the operations:

1. Iterating through all responses: O(m)
2. For each response, splitting into words: O(k)
3. Converting to set and iterating: O(k)
4. Overall counting phase: O(m * k)
5. Sorting features by count: O(n * log n)

The reference answer simplifies to O(n * log n) by assuming that m * k is typically smaller than n * log n in practical scenarios, or that the counting phase is considered a preprocessing step with the sorting being the dominant operation.

Space Complexity: O(m * k)

The space is used for:

• Counter dictionary storing at most O(m * k) unique words
• Temporary set for each response: O(k)
• Split words list for each response: O(k)

The overall space complexity is dominated by the Counter storage of unique words across all responses.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Counting Multiple Occurrences Within a Single Response

One of the most common mistakes is forgetting to use set() when processing each response, which would incorrectly count a feature multiple times if it appears repeatedly in the same response.

Incorrect Implementation:

# WRONG: This counts "camera" twice if a response says "camera camera"
for response in responses:
    for word in response.split():  # No set() used here
        word_frequency[word] += 1

Correct Implementation:

# CORRECT: Using set() ensures each word counts only once per response
for response in responses:
    for word in set(response.split()):
        word_frequency[word] += 1

2. Case Sensitivity Issues

The current solution is case-sensitive, meaning "Camera" and "camera" would be treated as different features. If the problem requires case-insensitive matching, you need to normalize the case.

Solution for Case-Insensitive Matching:

def sortFeatures(self, features: List[str], responses: List[str]) -> List[str]:
    word_frequency = Counter()
  
    # Create a mapping of lowercase to original feature names
    feature_map = {f.lower(): f for f in features}
  
    for response in responses:
        # Convert response to lowercase before processing
        unique_words = set(response.lower().split())
        for word in unique_words:
            word_frequency[word] += 1
  
    # Sort using lowercase version for lookup
    return sorted(features, key=lambda f: -word_frequency[f.lower()])

3. Partial Word Matching Confusion

The solution uses exact word matching after splitting by spaces. It won't match partial words or substrings. For example, if a feature is "battery" and a response contains "batteries", it won't be counted.

If Partial Matching is Required:

def sortFeatures(self, features: List[str], responses: List[str]) -> List[str]:
    feature_count = {feature: 0 for feature in features}
  
    for response in responses:
        response_lower = response.lower()
        for feature in features:
            # Check if feature appears as substring (not just whole word)
            if feature.lower() in response_lower:
                feature_count[feature] += 1
  
    return sorted(features, key=lambda f: -feature_count[f])

4. Assuming Features Are Always Present in Responses

The solution correctly handles features that never appear in responses (they get a count of 0), but developers might incorrectly assume all features will be mentioned and try to access counts directly without the Counter's default behavior.

Incorrect Assumption:

# WRONG: This would raise KeyError for features not in responses
regular_dict = {}
for response in responses:
    for word in set(response.split()):
        regular_dict[word] = regular_dict[word] + 1  # KeyError if word not in dict

Correct Handling:

# CORRECT: Counter handles missing keys gracefully
word_frequency = Counter()
# Counter returns 0 for missing keys, no KeyError