Find the Most Common Response solution and explanation
The 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.
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 <= 10001 <= responses[i].length <= 10001 <= responses[i][j].length <= 10responses[i][j]consists of only lowercase English letters
Approach overview
Problem Overview: You receive a collection of responses (strings) and must determine which response appears most frequently. The task is essentially a frequency counting problem where you track occurrences and return the response with the highest count.
Approach 1: Brute Force Frequency Counting (O(n²) time, O(1) space)
The most direct strategy compares every response with every other response and counts how many times each appears. For each index i, iterate through the entire list and count matching values. Track the maximum frequency encountered while scanning. This approach works without additional data structures but performs redundant comparisons, making it inefficient for large inputs. Time complexity is O(n²) and space complexity is O(1). It demonstrates the basic idea of counting occurrences but rarely passes strict performance constraints.
Approach 2: Sorting + Linear Scan (O(n log n) time, O(1) or O(n) space)
Sorting groups identical responses together so frequency counting becomes a single pass. First sort the array of responses. Then iterate through the sorted list and count consecutive duplicates, updating the most frequent response whenever a larger streak appears. Sorting costs O(n log n) time, while the scan is O(n). Extra space depends on the language’s sorting implementation (often O(1) to O(n)). This method is useful when modifying the array is allowed and you want a simple implementation without additional lookup structures.
Approach 3: Hash Table Counting (O(n) time, O(n) space)
The optimal solution uses a hash table to store frequency counts while iterating once through the responses. For each string, increment its counter in the map. During the same pass (or a follow-up scan of the map), track the response with the highest frequency. Hash table lookups and updates run in constant average time, producing overall O(n) time complexity with O(n) additional space for storing counts. This approach directly leverages common patterns from array traversal and counting problems, making it both efficient and straightforward to implement.
Recommended for interviews: Interviewers expect the hash table counting approach. Starting with the brute force explanation shows you understand the problem mechanics, but transitioning to a frequency map demonstrates algorithmic optimization. The HashMap/dict solution achieves linear time and clean logic, which is typically the target complexity for problems involving frequency analysis of strings.
Solution
We can use a hash table 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.
Finally, we iterate through the hash table to find the response with the highest count. If there are multiple responses with the same count, we return the lexicographically smallest one.
The complexity is O(L), and the space complexity is O(L), where L is the total length of all responses.
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 ansclass Solution {
public String findCommonResponse(List<List<String>> responses) {
Map<String, Integer> cnt = new HashMap<>();
for (var ws : responses) {
Set<String> s = new HashSet<>();
for (var w : ws) {
if (s.add(w)) {
cnt.merge(w, 1, Integer::sum);
}
}
}
String ans = responses.get(0).get(0);
for (var e : cnt.entrySet()) {
String w = e.getKey();
int v = e.getValue();
if (cnt.get(ans) < v || (cnt.get(ans) == v && w.compareTo(ans) < 0)) {
ans = w;
}
}
return ans;
}
}class Solution {
public:
string findCommonResponse(vector<vector<string>>& responses) {
unordered_map<string, int> cnt;
for (const auto& ws : responses) {
unordered_set<string> s;
for (const auto& w : ws) {
if (s.insert(w).second) {
++cnt[w];
}
}
}
string ans = responses[0][0];
for (const auto& e : cnt) {
const string& w = e.first;
int v = e.second;
if (cnt[ans] < v || (cnt[ans] == v && w < ans)) {
ans = w;
}
}
return ans;
}
};function findCommonResponse(responses: string[][]): string {
const cnt = new Map<string, number>();
for (const ws of responses) {
const s = new Set<string>();
for (const w of ws) {
if (!s.has(w)) {
s.add(w);
cnt.set(w, (cnt.get(w) ?? 0) + 1);
}
}
}
let ans = responses[0][0];
for (const [w, v] of cnt) {
const best = cnt.get(ans)!;
if (best < v || (best === v && w < ans)) {
ans = w;
}
}
return ans;
}func findCommonResponse(responses [][]string) string {
cnt := map[string]int{}
for _, ws := range responses {
s := map[string]struct{}{}
for _, w := range ws {
if _, ok := s[w]; !ok {
s[w] = struct{}{}
cnt[w]++
}
}
}
ans := responses[0][0]
for w, v := range cnt {
if cnt[ans] < v || (cnt[ans] == v && w < ans) {
ans = w
}
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Counting | O(n²) | O(1) | Small datasets or when avoiding extra memory is critical |
| Sorting + Linear Scan | O(n log n) | O(1)–O(n) | When sorting is acceptable and you want a simple counting pass |
| Hash Table Counting | O(n) | O(n) | General case and expected interview solution for frequency problems |
Frequently asked questions
Is Find the Most Common Response easy or hard?
The problem is generally considered Medium difficulty because it requires recognizing the frequency counting pattern and choosing the correct data structure. The logic is straightforward once you identify that a hash table efficiently tracks occurrences.
Find the Most Common Response Python/Java solution
Python typically uses a dictionary or collections.Counter to count frequencies, while Java implementations rely on HashMap<String, Integer>. Both approaches iterate once through the array and update counts, achieving O(n) time complexity.
How to solve Find the Most Common Response in O(n)?
Use a hash map where each response string is a key and the value stores its frequency. Iterate through the array and increment the counter for each occurrence. Track the maximum frequency during the traversal or after building the map, resulting in linear O(n) time.
What is the best approach for Find the Most Common Response?
The hash table counting approach is the most efficient and commonly expected solution. Iterate through the responses once, store frequencies in a hash map, and track the response with the highest count. This method runs in O(n) time with O(n) extra space.
Is Find the Most Common Response asked at Google/Amazon/Meta?
Frequency counting problems using hash maps appear frequently in interviews at companies like Google, Amazon, and Meta. Variants include finding the most frequent element, top K frequent elements, or grouping strings by frequency patterns.
What data structure is used in Find the Most Common Response?
A hash table (such as Python's dict, Java's HashMap, or C++ unordered_map) is the primary data structure. It allows constant average-time insertion and lookup, making it ideal for counting occurrences of strings.
What is the time complexity of Find the Most Common Response?
The optimal solution runs in O(n) time using a hash table to count frequencies while scanning the responses once. Alternative methods include sorting with O(n log n) time or brute force comparison with O(n²) time.