How hard is LeetCode 1772. Sort Features by Popularity?

LeetCode 1772. Sort Features by Popularity is rated Medium on LeetCode.

What is the time complexity of LeetCode 1772. Sort Features by Popularity?

The Python solution on this page runs in O(n \times \log n), where n is the length of `features`.

What is the space complexity of LeetCode 1772. Sort Features by Popularity?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 1772. Sort Features by Popularity cover?

LeetCode 1772. Sort Features by Popularity is tagged Array, Hash Table, String and Sorting on LeetCode.

Is LeetCode 1772. Sort Features by Popularity a premium problem?

Yes. LeetCode 1772. Sort Features by Popularity is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Sort Features by Popularity — LeetCode 1772 Python Solution

MediumLeetCode PremiumArrayHash TableStringSorting

Problem: #1772
Pattern: Sorting
Reading time: 2 min
Source: leetcode.com

The 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.

Example

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.

Python solution

Python

class Solution:
    def sortFeatures(self, features: List[str], responses: List[str]) -> List[str]:
        cnt = Counter()
        for s in responses:
            for w in set(s.split()):
                cnt[w] += 1
        return sorted(features, key=lambda w: -cnt[w])

Complexity

Measure	Complexity
Time	O(n \times \log n), where n is the length of `features`
Space	O(n) auxiliary

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 1772. Sort Features by Popularity is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1772. Sort Features by Popularity?: LeetCode 1772. Sort Features by Popularity is rated Medium on LeetCode.
What is the time complexity of LeetCode 1772. Sort Features by Popularity?: The Python solution on this page runs in O(n \times \log n), where n is the length of `features`.
What is the space complexity of LeetCode 1772. Sort Features by Popularity?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1772. Sort Features by Popularity cover?: LeetCode 1772. Sort Features by Popularity is tagged Array, Hash Table, String and Sorting on LeetCode.
Is LeetCode 1772. Sort Features by Popularity a premium problem?: Yes. LeetCode 1772. Sort Features by Popularity is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.