# Find the Most Common Response
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-most-common-response)
Canonical: https://scaleengineer.com/dsa/problems/find-the-most-common-response
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table, String
---
## 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 <= 1000`
* `1 <= responses[i].length <= 1000`
* `1 <= responses[i][j].length <= 10`
* `responses[i][j]` consists of only lowercase English letters

# Approaches
## Brute-Force by Iterating Over All Unique Words
This approach first identifies all unique responses that exist across all days. Then, for each of these unique responses, it iterates through every single day's list to count how many days it appears in. This involves a significant amount of repeated work, as each day's list is processed multiple times, once for every unique word in the entire dataset.
**Time:** O(U * N * M * L), where `U` is the total number of unique strings, `N` is the number of days, `M` is the max responses per day, and `L` is the max string length. Since `U` can be up to `O(N * M)`, the complexity can approach `O(N^2 * M^2 * L)`, which is very slow. · **Space:** O(U * L), where `U` is the total number of unique strings across all days and `L` is the max string length. In the worst case, this is `O(N * M * L)`, where `N` is the number of days and `M` is the max responses per day. This space is used for the master set of unique responses and the frequency map.
**Pros:** Conceptually straightforward to break down into distinct steps.
**Cons:** Extremely inefficient due to multiple nested loops.; The time complexity is very high, making it impractical for the given constraints.; Performs a lot of redundant work by repeatedly creating `HashSet`s for each day for every unique word.
### Explanation
The core idea is to first find the complete dictionary of possible responses and then count the occurrences for each. 

- **Step 1: Collect All Unique Words:** We iterate through the entire 2D array and add every single response to a `HashSet`. This gives us a set of all unique words that appear anywhere in the survey.

- **Step 2: Count Frequencies:** We then iterate through our set of unique words. For each word, we start a counter at zero. We then loop through all the days again. For each day, we create another `HashSet` of that day's responses (to handle duplicates within that day) and check if our target word is present. If it is, we increment our counter. After checking all days, we store the final count in a `HashMap`.

- **Step 3: Find the Winner:** After counting is done for all unique words, we iterate through our frequency map to find the word with the highest count, making sure to handle ties by choosing the lexicographically smallest word.

```java
import java.util.*;

class Solution {
    public String mostCommonWord(String[][] responses) {
        Set<String> allUniqueResponses = new HashSet<>();
        for (String[] dayResponses : responses) {
            for (String response : dayResponses) {
                allUniqueResponses.add(response);
            }
        }

        Map<String, Integer> counts = new HashMap<>();
        for (String uniqueResponse : allUniqueResponses) {
            int currentCount = 0;
            for (String[] dayResponses : responses) {
                Set<String> dailyUnique = new HashSet<>(Arrays.asList(dayResponses));
                if (dailyUnique.contains(uniqueResponse)) {
                    currentCount++;
                }
            }
            counts.put(uniqueResponse, currentCount);
        }

        String mostCommon = "";
        int maxFreq = -1;

        for (Map.Entry<String, Integer> entry : counts.entrySet()) {
            String response = entry.getKey();
            int freq = entry.getValue();
            if (freq > maxFreq) {
                maxFreq = freq;
                mostCommon = response;
            } else if (freq == maxFreq) {
                if (mostCommon.isEmpty() || response.compareTo(mostCommon) < 0) {
                    mostCommon = response;
                }
            }
        }

        return mostCommon;
    }
}
```
### Algorithm
- Create a master `HashSet` called `allUniqueResponses`.
- Iterate through each day's `responses[i]` and add all strings to `allUniqueResponses`. This gives us a set of every unique response that exists in the entire dataset.
- Initialize a `HashMap<String, Integer> counts` to store the frequency of each unique response.
- Iterate through each `response` in `allUniqueResponses`.
- For each `response`, iterate through all the days from `i = 0` to `responses.length - 1`.
- Inside the day loop, create a temporary `HashSet` from `responses[i]` to handle duplicates for that specific day.
- Check if the current `response` is present in the temporary `HashSet`. If it is, increment its count in the `counts` map.
- After populating the `counts` map, iterate through its entries to find the response with the highest frequency.
- Maintain a `result` string and a `maxFreq` integer. Update them based on the frequency and lexicographical order for ties.
- Return the final `result`.

## Single-Pass Counting with Hash Map
This is the standard and efficient approach for this problem. It iterates through the responses day by day, removes duplicates for each day using a `HashSet`, and aggregates the counts of these unique daily responses into a global `HashMap`. By processing each day's unique responses only once and updating the potential answer on the fly, it avoids the redundant computations of the brute-force method.
**Time:** O(T * L), where `T` is the total number of responses across all days (sum of all `responses[i].length`), and `L` is the maximum length of a response string. This can also be expressed as `O(N * M * L)` where `N` is the number of days and `M` is the maximum responses per day. Each response string is processed a constant number of times. · **Space:** O(U * L), where `U` is the total number of unique strings across all days and `L` is the max string length. In the worst case, this is `O(N * M * L)`. This space is used for the frequency map and the temporary set for each day's responses.
**Pros:** Highly efficient in time, processing the data in a single logical pass.; Well-suited for the given constraints.; The use of `HashMap` and `HashSet` provides fast average-case lookups and insertions.
**Cons:** Requires extra space for the `HashMap` and `HashSet`, which could be significant if the number of unique responses is very large.
### Explanation
This method processes the data in a single pass, which is much more efficient. Instead of finding all unique words first, we count them as we encounter them.

- **Step 1: Initialize Data Structures:** We need a `HashMap<String, Integer>` to store the frequency of each response. We also initialize variables `result` and `maxFreq` to keep track of the most common response found so far.

- **Step 2: Process Day by Day:** We loop through each day's list of responses. For each day, we first put its responses into a `HashSet`. This is a quick way to get only the unique responses for that day.

- **Step 3: Update Counts and Track Winner:** We then iterate through this set of unique daily responses. For each response, we update its count in our main `HashMap`. Immediately after updating a count, we check if this response has become the new winner. 
  - We compare its new frequency with `maxFreq`. If it's greater, this response becomes the new `result`.
  - If the frequency is equal to `maxFreq`, we resolve the tie by comparing it lexicographically with the current `result` and updating if the new response is smaller.

This way, when the loops are finished, we have our final answer without needing a separate step to find the winner.

```java
import java.util.*;

class Solution {
    public String mostCommonWord(String[][] responses) {
        Map<String, Integer> counts = new HashMap<>();
        String result = "";
        int maxFreq = 0;

        for (String[] dayResponses : responses) {
            Set<String> uniqueDailyResponses = new HashSet<>(Arrays.asList(dayResponses));
            for (String response : uniqueDailyResponses) {
                int newFreq = counts.getOrDefault(response, 0) + 1;
                counts.put(response, newFreq);

                if (newFreq > maxFreq) {
                    maxFreq = newFreq;
                    result = response;
                } else if (newFreq == maxFreq) {
                    if (response.compareTo(result) < 0) {
                        result = response;
                    }
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize a `HashMap<String, Integer> counts` to store frequencies.
- Initialize `result = ""` and `maxFreq = 0` to track the winner in real-time.
- Iterate through each day's responses `dayResponses` in the input `responses`.
- For each `dayResponses`, create a `HashSet<String>` to get the unique responses for that day. This efficiently handles the duplicate removal requirement for each day.
- Iterate through the unique responses from the daily `HashSet`.
- For each unique `response`, increment its count in the global `counts` map and get its `newFreq`.
- Compare `newFreq` with `maxFreq`:
  - If `newFreq > maxFreq`, a new most common word is found. Update `maxFreq = newFreq` and `result = response`.
  - If `newFreq == maxFreq`, there is a tie. Check if the current `response` is lexicographically smaller than the current `result`. If so, update `result`.
- After iterating through all days, `result` will hold the correct answer.

# Solutions
### Java

```java
class 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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```