Find the Most Common Response

Problem

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

Return the most common response across all days after removing duplicate responses within each responses[i]. If there is a tie, return the lexicographically smallest response.

Examples

Example 1

Input: responses =
[["good","ok","good","ok"],["ok","bad","good","ok","ok"],["good"],["bad"]]
Output: "good"
Explanation:
* After removing duplicates within each list, `responses = [["good", "ok"], ["ok", "bad", "good"], ["good"], ["bad"]]`.
* `"good"` appears 3 times, `"ok"` appears 2 times, and `"bad"` appears 2 times.
* Return `"good"` because it has the highest frequency.

Example 2

Input: responses =
[["good","ok","good"],["ok","bad"],["bad","notsure"],["great","good"]]
Output: "bad"
Explanation:
* After removing duplicates within each list we have `responses = [["good", "ok"], ["ok", "bad"], ["bad", "notsure"], ["great", "good"]]`.
* `"bad"`, `"good"`, and `"ok"` each occur 2 times.
* The output is `"bad"` because it is the lexicographically smallest amongst the words with the highest frequency.

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

Method 1 – Hash Map Counting with Set Deduplication

Intuition

To find the most common response, first remove duplicates within each day's responses, then count the frequency of each unique response across all days. In case of a tie, return the lexicographically smallest response.

Approach

1. For each day's responses, convert the list to a set to remove duplicates.
2. Use a hash map (dictionary) to count the frequency of each response across all days.
3. Find the response with the highest frequency. If there is a tie, choose the lexicographically smallest one.
4. Return the result.

Code

C++

class Solution {
public:
    string mostCommonResponse(vector<vector<string>>& responses) {
        unordered_map<string, int> cnt;
        for(auto& day : responses) {
            unordered_set<string> seen(day.begin(), day.end());
            for(auto& resp : seen) cnt[resp]++;
        }
        string ans;
        int mx = 0;
        for(auto& [resp, c] : cnt) {
            if(c > mx || (c == mx && resp < ans)) {
                mx = c;
                ans = resp;
            }
        }
        return ans;
    }
};

Go

func mostCommonResponse(responses [][]string) string {
    cnt := map[string]int{}
    for _, day := range responses {
        seen := map[string]bool{}
        for _, resp := range day {
            seen[resp] = true
        }
        for resp := range seen {
            cnt[resp]++
        }
    }
    ans := ""
    mx := 0
    for resp, c := range cnt {
        if c > mx || (c == mx && (ans == "" || resp < ans)) {
            mx = c
            ans = resp
        }
    }
    return ans
}

Java

class Solution {
    public String mostCommonResponse(List<List<String>> responses) {
        Map<String, Integer> cnt = new HashMap<>();
        for(List<String> day : responses) {
            Set<String> seen = new HashSet<>(day);
            for(String resp : seen) cnt.put(resp, cnt.getOrDefault(resp, 0)+1);
        }
        String ans = "";
        int mx = 0;
        for(var e : cnt.entrySet()) {
            String resp = e.getKey(); int c = e.getValue();
            if(c > mx || (c == mx && (ans.equals("") || resp.compareTo(ans) < 0))) {
                mx = c;
                ans = resp;
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun mostCommonResponse(responses: List<List<String>>): String {
        val cnt = mutableMapOf<String, Int>()
        for (day in responses) {
            val seen = day.toSet()
            for (resp in seen) cnt[resp] = cnt.getOrDefault(resp, 0) + 1
        }
        var ans = ""
        var mx = 0
        for ((resp, c) in cnt) {
            if (c > mx || (c == mx && (ans == "" || resp < ans))) {
                mx = c
                ans = resp
            }
        }
        return ans
    }
}

Python

class Solution:
    def mostCommonResponse(self, responses: list[list[str]]) -> str:
        from collections import Counter
        cnt = Counter()
        for day in responses:
            for resp in set(day):
                cnt[resp] += 1
        mx = max(cnt.values())
        return min([resp for resp, c in cnt.items() if c == mx])

Rust

use std::collections::{HashMap, HashSet};
impl Solution {
    pub fn most_common_response(responses: Vec<Vec<String>>) -> String {
        let mut cnt = HashMap::new();
        for day in responses {
            let seen: HashSet<_> = day.iter().collect();
            for resp in seen {
                *cnt.entry(resp).or_insert(0) += 1;
            }
        }
        let mut ans = String::new();
        let mut mx = 0;
        for (resp, &c) in &cnt {
            if c > mx || (c == mx && (ans.is_empty() || resp < &ans)) {
                mx = c;
                ans = resp.clone();
            }
        }
        ans
    }
}

TypeScript

class Solution {
    mostCommonResponse(responses: string[][]): string {
        const cnt = new Map<string, number>();
        for(const day of responses) {
            const seen = new Set(day);
            for(const resp of seen) cnt.set(resp, (cnt.get(resp)||0)+1);
        }
        let ans = "";
        let mx = 0;
        for(const [resp, c] of cnt.entries()) {
            if(c > mx || (c === mx && (ans === "" || resp < ans))) {
                mx = c;
                ans = resp;
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(N), where N is the total number of responses.
• 🧺 Space complexity: O(N), for the hash map and sets.