Sort Features by Popularity

Problem

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.

Examples

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

Method 1 - Hash Map Counting with Custom Sorting

Intuition

Count how many responses mention each feature (counting each feature at most once per response), then sort by popularity descending and by original index ascending for ties.

Approach

1. Count popularity of each feature across all responses
2. For each response, convert to set of words to avoid double counting
3. Create pairs of (feature, popularity, original_index)
4. Sort by popularity descending, then by original index ascending
5. Extract sorted features

Code

C++

#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<string> sortFeatures(vector<string>& features, vector<string>& responses) {
        unordered_map<string, int> popularity;
        
        // Count popularity of each feature
        for (const string& response : responses) {
            unordered_set<string> wordsInResponse;
            stringstream ss(response);
            string word;
            
            while (ss >> word) {
                wordsInResponse.insert(word);
            }
            
            for (const string& word : wordsInResponse) {
                popularity[word]++;
            }
        }
        
        // Create vector with feature, popularity, and original index
        vector<tuple<string, int, int>> featureData;
        for (int i = 0; i < features.size(); i++) {
            int pop = popularity.count(features[i]) ? popularity[features[i]] : 0;
            featureData.push_back({features[i], pop, i});
        }
        
        // Sort by popularity desc, then by original index asc
        sort(featureData.begin(), featureData.end(), 
             [](const auto& a, const auto& b) {
                 if (get<1>(a) == get<1>(b)) {
                     return get<2>(a) < get<2>(b);
                 }
                 return get<1>(a) > get<1>(b);
             });
        
        vector<string> result;
        for (const auto& data : featureData) {
            result.push_back(get<0>(data));
        }
        
        return result;
    }
};

Go

import (
    "sort"
    "strings"
)

func sortFeatures(features []string, responses []string) []string {
    popularity := make(map[string]int)
    
    // Count popularity of each feature
    for _, response := range responses {
        wordsInResponse := make(map[string]bool)
        words := strings.Fields(response)
        
        for _, word := range words {
            wordsInResponse[word] = true
        }
        
        for word := range wordsInResponse {
            popularity[word]++
        }
    }
    
    // Create slice with feature data
    type FeatureData struct {
        feature string
        pop     int
        index   int
    }
    
    var featureData []FeatureData
    for i, feature := range features {
        pop := popularity[feature]
        featureData = append(featureData, FeatureData{feature, pop, i})
    }
    
    // Sort by popularity desc, then by original index asc
    sort.Slice(featureData, func(i, j int) bool {
        if featureData[i].pop == featureData[j].pop {
            return featureData[i].index < featureData[j].index
        }
        return featureData[i].pop > featureData[j].pop
    })
    
    result := make([]string, len(features))
    for i, data := range featureData {
        result[i] = data.feature
    }
    
    return result
}

Java

import java.util.*;

class Solution {
    public String[] sortFeatures(String[] features, String[] responses) {
        Map<String, Integer> popularity = new HashMap<>();
        
        // Count popularity of each feature
        for (String response : responses) {
            Set<String> wordsInResponse = new HashSet<>();
            String[] words = response.split(" ");
            
            for (String word : words) {
                wordsInResponse.add(word);
            }
            
            for (String word : wordsInResponse) {
                popularity.put(word, popularity.getOrDefault(word, 0) + 1);
            }
        }
        
        // Create list with feature data
        List<int[]> featureData = new ArrayList<>();
        for (int i = 0; i < features.length; i++) {
            int pop = popularity.getOrDefault(features[i], 0);
            featureData.add(new int[]{i, pop}); // {originalIndex, popularity}
        }
        
        // Sort by popularity desc, then by original index asc
        featureData.sort((a, b) -> {
            if (a[1] == b[1]) {
                return Integer.compare(a[0], b[0]);
            }
            return Integer.compare(b[1], a[1]);
        });
        
        String[] result = new String[features.length];
        for (int i = 0; i < featureData.size(); i++) {
            result[i] = features[featureData.get(i)[0]];
        }
        
        return result;
    }
}

Kotlin

class Solution {
    fun sortFeatures(features: Array<String>, responses: Array<String>): Array<String> {
        val popularity = mutableMapOf<String, Int>()
        
        // Count popularity of each feature
        for (response in responses) {
            val wordsInResponse = response.split(" ").toSet()
            
            for (word in wordsInResponse) {
                popularity[word] = popularity.getOrDefault(word, 0) + 1
            }
        }
        
        // Create list with feature data
        val featureData = features.mapIndexed { index, feature ->
            Triple(feature, popularity.getOrDefault(feature, 0), index)
        }
        
        // Sort by popularity desc, then by original index asc
        val sorted = featureData.sortedWith { a, b ->
            when {
                a.second != b.second -> b.second.compareTo(a.second)
                else -> a.third.compareTo(b.third)
            }
        }
        
        return sorted.map { it.first }.toTypedArray()
    }
}

Python

def sortFeatures(features: list[str], responses: list[str]) -> list[str]:
    popularity = {}
    
    # Count popularity of each feature
    for response in responses:
        words_in_response = set(response.split())
        
        for word in words_in_response:
            popularity[word] = popularity.get(word, 0) + 1
    
    # Create list with feature data: (feature, popularity, original_index)
    feature_data = []
    for i, feature in enumerate(features):
        pop = popularity.get(feature, 0)
        feature_data.append((feature, pop, i))
    
    # Sort by popularity desc, then by original index asc
    feature_data.sort(key=lambda x: (-x[1], x[2]))
    
    return [feature for feature, _, _ in feature_data]

# Alternative using Counter
from collections import Counter

def sortFeatures2(features: list[str], responses: list[str]) -> list[str]:
    popularity = Counter()
    
    for response in responses:
        words_in_response = set(response.split())
        popularity.update(words_in_response)
    
    # Sort features by popularity desc, then by original index asc
    return sorted(features, key=lambda x: (-popularity[x], features.index(x)))

Rust

use std::collections::{HashMap, HashSet};

impl Solution {
    pub fn sort_features(features: Vec<String>, responses: Vec<String>) -> Vec<String> {
        let mut popularity: HashMap<String, i32> = HashMap::new();
        
        // Count popularity of each feature
        for response in &responses {
            let words_in_response: HashSet<&str> = response.split_whitespace().collect();
            
            for word in words_in_response {
                *popularity.entry(word.to_string()).or_insert(0) += 1;
            }
        }
        
        // Create vector with feature data
        let mut feature_data: Vec<(String, i32, usize)> = Vec::new();
        for (i, feature) in features.iter().enumerate() {
            let pop = popularity.get(feature).unwrap_or(&0);
            feature_data.push((feature.clone(), *pop, i));
        }
        
        // Sort by popularity desc, then by original index asc
        feature_data.sort_by(|a, b| {
            if a.1 == b.1 {
                a.2.cmp(&b.2)
            } else {
                b.1.cmp(&a.1)
            }
        });
        
        feature_data.into_iter().map(|(feature, _, _)| feature).collect()
    }
}

TypeScript

function sortFeatures(features: string[], responses: string[]): string[] {
    const popularity = new Map<string, number>();
    
    // Count popularity of each feature
    for (const response of responses) {
        const wordsInResponse = new Set(response.split(' '));
        
        for (const word of wordsInResponse) {
            popularity.set(word, (popularity.get(word) || 0) + 1);
        }
    }
    
    // Create array with feature data
    const featureData: [string, number, number][] = [];
    for (let i = 0; i < features.length; i++) {
        const pop = popularity.get(features[i]) || 0;
        featureData.push([features[i], pop, i]);
    }
    
    // Sort by popularity desc, then by original index asc
    featureData.sort((a, b) => {
        if (a[1] === b[1]) {
            return a[2] - b[2];
        }
        return b[1] - a[1];
    });
    
    return featureData.map(data => data[0]);
}

Complexity

• ⏰ Time complexity: O(R * W + F log F) where R is number of responses, W is average words per response, F is number of features
• 🧺 Space complexity: O(R * W + F) for storing word sets and feature data