1772. Sort Features by Popularity
Explanation:
To solve this problem, we need to sort the features based on their popularity. The popularity is defined as the total number of requests that contain a particular feature. If two features have the same popularity, they should be ordered lexicographically.
We can achieve this by following these steps:
- Create a map to store the feature as key and its popularity as the value.
- Iterate through the requests and update the popularity of each feature in the map.
- Sort the features based on their popularity. If two features have the same popularity, we sort them lexicographically.
- Return the sorted list of features.
Time Complexity:
The time complexity of this approach is O(n * m * log(m)), where n is the number of requests and m is the average length of a request.
Space Complexity:
The space complexity is O(m*n) for storing the features and their popularity.
:
import java.util.*;
class Solution {
public List<String> sortFeatures(String[] features, String[] responses) {
Map<String, Integer> featurePopularity = new HashMap<>();
for (String response : responses) {
Set<String> seen = new HashSet<>();
for (String feature : features) {
if (response.contains(feature) && !seen.contains(feature)) {
featurePopularity.put(feature, featurePopularity.getOrDefault(feature, 0) + 1);
seen.add(feature);
}
}
}
List<String> sortedFeatures = new ArrayList<>(Arrays.asList(features));
Collections.sort(sortedFeatures, (a, b) -> (featurePopularity.get(b) - featurePopularity.get(a) == 0 ? a.compareTo(b) : featurePopularity.get(b) - featurePopularity.get(a)));
return sortedFeatures;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.