Facebook Pixel

3527. Find the Most Common Response

MediumArrayHash TableStringCounting
Leetcode Link

Problem Description

You are given a 2D string array responses where each responses[i] is an array of strings representing survey responses from the i-th day.

The task is to return the most common response across all days after removing duplicate responses within each responses[i]. If there is a tie in the frequency of responses, return the lexicographically smaller response.

Intuition

To solve this problem, the key steps involve deduplicating the responses for each day and then counting how often each unique response appears across all days.

  1. Remove Duplicates: For each day's responses, convert the list of responses into a set to automatically eliminate any duplicate responses from that day. This ensures that each response from a day contributes only once to the overall count.

  2. Count Occurrences: Use a hash table (or dictionary) to track how many times each unique response appears across all the days.

  3. Determine the Frequent Response: After populating the hash table with all responses, iterate through the hash table to find the response with the highest occurrence count. In case of a tie (multiple responses with the same count), select the lexicographically smallest response. This approach ensures the answer is the most common response or, in case of ties, the smallest in dictionary order.

Solution Approach

To implement the solution, we follow these steps:

  1. Use a Hash Table: Initialize a counter using a hash table (or Counter from the collections module) to keep track of each unique response's count.

  2. Iterate Over Each Day's Responses:

    • For each responses[i], convert it into a set to remove any duplicates. This ensures each response from a day is counted only once, regardless of how many times it appears on that particular day.
    • For each unique response in this set, increment its count in the hash table.

  3. Determine the Most Common Response:

    • Initialize a variable ans to keep track of the response with the highest count. Start by setting it to the first response from the first day's list.
    • Traverse the hash table: For each entry, if the corresponding count is higher than ans's count, update ans to this response. If the count is the same but the current response is lexicographically smaller than ans, then also update ans.

  4. Return the Result:

    • After processing all responses, ans will contain the most frequent response or the lexicographically smallest one in case of a tie. Return ans.

The code implementing this approach is:

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

This solution efficiently counts the responses and resolves ties appropriately using both frequency and lexicographic comparisons.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through an example to understand the solution approach. Suppose we have the following responses array:

responses = [
    ["apple", "banana", "apple"],
    ["banana", "pear", "banana"],
    ["pear", "banana", "apple"]
]

Step 1: Remove Duplicates

  • For Day 1: responses[0] = ["apple", "banana", "apple"]. Convert to set: {"apple", "banana"}
  • For Day 2: responses[1] = ["banana", "pear", "banana"]. Convert to set: {"banana", "pear"}
  • For Day 3: responses[2] = ["pear", "banana", "apple"]. Convert to set: {"apple", "banana", "pear"}

Step 2: Count Occurrences

  • Initialize a counter cnt = {}.
  • For Day 1 set: {"apple", "banana"}, update cnt to: {"apple": 1, "banana": 1}
  • For Day 2 set: {"banana", "pear"}, update cnt to: {"apple": 1, "banana": 2, "pear": 1}
  • For Day 3 set: {"apple", "banana", "pear"}, update cnt to: {"apple": 2, "banana": 3, "pear": 2}

Step 3: Determine the Most Common Response

  • Initialize ans with the first response: ans = "apple"
  • Traverse cnt:
    • For "apple": cnt["apple"] = 2
    • For "banana": cnt["banana"] = 3, update ans to "banana" since 3 > 2
    • For "pear": cnt["pear"] = 2, do not update ans as cnt["pear"] < cnt["banana"]

Step 4: Return the Result

  • The most common response is "banana", as it appears 3 times across all days. Return "banana".

This algorithm effectively handles duplicate entries per day and resolves ties by selecting the lexicographically smaller string when counts are the same.

Solution Implementation

1from typing import List
2from collections import Counter
3
4class Solution:
5    def findCommonResponse(self, responses: List[List[str]]) -> str:
6        # Initialize a counter to keep track of the frequency of each unique word
7        frequency_counter = Counter()
8      
9        # Iterate over each sublist in the responses
10        for word_list in responses:
11            # Convert the list into a set to consider each word only once per response
12            unique_words = set(word_list)
13            # Increment the count for each unique word
14            for word in unique_words:
15                frequency_counter[word] += 1
16      
17        # Assume the first response's first word is the most common initially
18        most_common_word = responses[0][0]
19      
20        # Iterate through each word and its count in the frequency counter
21        for word, count in frequency_counter.items():
22            # Update most_common_word based on higher frequency or lexicographical precedence
23            if frequency_counter[most_common_word] < count or (frequency_counter[most_common_word] == count and word < most_common_word):
24                most_common_word = word
25      
26        # Return the most common word
27        return most_common_word
28
1import java.util.List;
2import java.util.Map;
3import java.util.HashMap;
4import java.util.HashSet;
5import java.util.Set;
6
7class Solution {
8    public String findCommonResponse(List<List<String>> responses) {
9        // A map to hold the frequency of each word
10        Map<String, Integer> wordCount = new HashMap<>();
11
12        // Iterate over each list of responses
13        for (List<String> responseList : responses) {
14            // A set to keep track of unique words in the current response list
15            Set<String> uniqueWords = new HashSet<>();
16
17            // Iterate over each word in the current list
18            for (String word : responseList) {
19                // Add word to unique words set; if successfully added, update word count
20                if (uniqueWords.add(word)) {
21                    // If the word is newly encountered, initialize its count
22                    // Otherwise, increment the existing count
23                    wordCount.merge(word, 1, Integer::sum);
24                }
25            }
26        }
27
28        // Initially, assume the first word of the first response list is the most common
29        String mostCommonWord = responses.get(0).get(0);
30
31        // Iterate over the word count entries to find the most common word
32        for (Map.Entry<String, Integer> entry : wordCount.entrySet()) {
33            String word = entry.getKey();
34            int count = entry.getValue();
35
36            // Update the most common word based on frequency
37            // If a word has a higher frequency, or if the frequencies are the same and the word is lexicographically smaller, update
38            if (wordCount.get(mostCommonWord) < count || 
39                (wordCount.get(mostCommonWord) == count && word.compareTo(mostCommonWord) < 0)) {
40                mostCommonWord = word;
41            }
42        }
43
44        // Return the word with highest frequency (and smallest lexicographically if there is a tie)
45        return mostCommonWord;
46    }
47}
48
1class Solution {
2public:
3    string findCommonResponse(vector<vector<string>>& responses) {
4        unordered_map<string, int> wordCount; // Map to keep track of word frequencies
5
6        // Iterate over each list of responses
7        for (const auto& responseList : responses) {
8            unordered_set<string> uniqueWords; // Set to ensure each word is counted only once per response list
9
10            // Iterate over each word in the current response list
11            for (const auto& word : responseList) {
12                // If the word was inserted successfully (i.e., it's the first occurrence in this list)
13                if (uniqueWords.insert(word).second) {
14                    ++wordCount[word]; // Increment the count for this word
15                }
16            }
17        }
18      
19        // Initialize the most common word with the first word from the first response list
20        string mostCommonWord = responses[0][0];
21
22        // Iterate over the word count map to find the most common word
23        for (const auto& entry : wordCount) {
24            const string& word = entry.first;
25            int count = entry.second;
26
27            // Update the most common word if the current word has a higher count
28            // or the same count but lexicographically smaller than the current most common word
29            if (wordCount[mostCommonWord] < count || 
30               (wordCount[mostCommonWord] == count && word < mostCommonWord)) {
31                mostCommonWord = word;
32            }
33        }
34      
35        return mostCommonWord; // Return the word that is the most common across all responses
36    }
37};
38
1// Function to find the most common response among a list of responses
2function findCommonResponse(responses: string[][]): string {
3    // Create a map to count occurrences of each word
4    const wordCount = new Map<string, number>();
5  
6    // Iterate over each list of words (ws) in the responses
7    for (const wordsList of responses) {
8        // Use a set to ensure each word is counted only once per response
9        const uniqueWords = new Set<string>();
10
11        // Iterate over each word in the current list
12        for (const word of wordsList) {
13            // If the word is not already in the set, add it
14            if (!uniqueWords.has(word)) {
15                uniqueWords.add(word);
16                // Increment the count for this word in the map
17                wordCount.set(word, (wordCount.get(word) ?? 0) + 1);
18            }
19        }
20    }
21
22    // Initialize the answer with the first word of the first response
23    let mostCommonWord = responses[0][0];
24  
25    // Iterate over the word-count map to find the most common word
26    for (const [word, count] of wordCount) {
27        const currentBestCount = wordCount.get(mostCommonWord)!;
28
29        // Update the most common word if current word has a higher count
30        // or has the same count but is lexicographically smaller
31        if (currentBestCount < count || (currentBestCount === count && word < mostCommonWord)) {
32            mostCommonWord = word;
33        }
34    }
35  
36    // Return the most common word found
37    return mostCommonWord;
38}
39

Time and Space Complexity

The given code's time complexity is O(L), where L is the total length of all responses. This is because each word in each response is processed a constant number of times (once to convert the list to a set and once when updating the counter).

The space complexity is also O(L). This is due to the use of a Counter object to store the frequency of each unique word across all responses, which in the worst case can hold all distinct words from all responses.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following problems can be solved with backtracking (select multiple)

Recommended Readings

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More