#3527

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find the Most Common Response

Find the most common survey response after eliminating duplicates within each day, using array scanning and hash lookups.

array hash table string counting

Problem Statement

You are given a 2D array responses, where each responses[i] represents survey responses for the ith day. The task is to determine the most frequent unique response across all days after removing duplicates within each individual day's response array.

If there is a tie for the most frequent response, return the lexicographically smallest one. Your solution should be efficient enough to handle up to 1,000 days and 1,000 responses per day, making array scanning and hash lookup important to solving the problem.

Examples

Example 1

Input: responses = [["good","ok","good","ok"],["ok","bad","good","ok","ok"],["good"],["bad"]]

Output: "good"

Example 2

Input: responses = [["good","ok","good"],["ok","bad"],["bad","notsure"],["great","good"]]

Output: "bad"

Constraints

1 <= responses.length <= 1000
1 <= responses[i].length <= 1000
1 <= responses[i][j].length <= 10
responses[i][j] consists of only lowercase English letters

Solution Approach

Step 1: Remove Duplicates Within Each Day

The first step is to ensure that there are no duplicates within each day's response array. This can be achieved by converting each day's list of responses into a set, which automatically removes duplicates.

Step 2: Count Frequency of Each Response

After eliminating duplicates within each day, you can count the frequency of each unique response using a hash table (or HashMap). This will help efficiently track the occurrence of each response across all the days.

Step 3: Find the Most Common Response

After counting the frequencies, you need to find the response with the highest count. In case of a tie (same frequency), the lexicographically smaller response should be returned. This can be done using simple comparison logic while iterating through the frequency map.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is determined by the need to process each response within each day, resulting in O(N * M) where N is the number of days and M is the average number of responses per day. The space complexity is O(N * M) to store the responses and their counts in the hash map.

What Interviewers Usually Probe

Can the candidate efficiently handle large input sizes?
Does the candidate apply hash maps effectively for counting frequencies?
How well does the candidate handle tie-breaking between lexicographically equal counts?

Common Pitfalls or Variants

Common pitfalls

Not removing duplicates within each day before counting frequencies can lead to incorrect results.
Failure to account for ties in frequency, which may lead to returning the wrong response.
Inefficient handling of large input sizes, especially with array scanning or hash lookup.

Follow-up variants

Handle responses with varying case sensitivity (e.g., 'good' vs 'Good').
Find the second most common response instead of the first.
Return the least common response instead of the most common.

FAQ

What is the main pattern used in 'Find the Most Common Response'?

The primary pattern is array scanning combined with hash map lookup to efficiently count occurrences and handle ties.

How do I handle ties in the frequency of responses?

If multiple responses have the same frequency, return the lexicographically smallest one.

What is the time complexity of this problem?

The time complexity is O(N * M), where N is the number of days and M is the number of responses per day.

Why do I need to remove duplicates within each day?

Duplicates within each day would distort the frequency count and lead to incorrect results. Removing them ensures accuracy.

Can I solve this problem without using hash maps?

While it's possible, hash maps provide an efficient way to count frequencies and are optimal for this task, especially with large inputs.

terminal

Solution

Solution 1: Hash Table

We can use a hash table $\textit{cnt}$ to count the occurrences of each response. For the responses of each day, we first remove duplicates, then add each response to the hash table and update its count.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def findCommonResponse(self, responses: List[List[str]]) -> str:
        cnt = Counter()
        for ws in responses:
            for w in set(ws):
                cnt[w] += 1
        ans = responses[0][0]
        for w, x in cnt.items():
            if cnt[ans] < x or (cnt[ans] == x and w < ans):
                ans = w
        return ans

Continue Practicing

#3035 maximum palindromes after operations #3522 calculate score after performing instructions #3518 smallest palindromic rearrangement ii