Problem Description

You are given a 2D string array responses where each responses[i] represents survey responses collected on day i.

Your task is to find the most common response across all days. However, there's an important rule: if the same response appears multiple times on the same day, it should only be counted once for that day.

For example:

• If day 1 has responses ["apple", "banana", "apple"], the response "apple" only counts once for day 1
• If day 2 has responses ["apple", "orange"], the response "apple" counts once for day 2
• In total, "apple" would have a count of 2 across both days

After counting all responses with duplicates removed per day, you need to return the response that appears on the most days. If multiple responses have the same maximum count, return the one that comes first lexicographically (alphabetically).

The solution uses a hash table to track how many days each unique response appears on. For each day's responses, it first converts them to a set to remove duplicates, then increments the count for each unique response. Finally, it finds the response with the highest count, breaking ties by choosing the lexicographically smallest one.

Intuition

The key insight is recognizing that we need to count how many days each response appears on, not the total number of times it appears across all days. This distinction is crucial because a response appearing multiple times on the same day should only contribute 1 to its overall count.

Think of it like counting attendance - if a student raises their hand multiple times in one class, they're still only present for one class session. Similarly, if "apple" appears 5 times on day 1, it still only counts as appearing on 1 day.

This naturally leads us to a two-step counting process:

1. For each day, identify the unique responses (removing duplicates within that day)
2. Count how many days each unique response appears across all days

Why use a set for each day? Converting responses[i] to a set automatically removes duplicates, giving us exactly what we need - the distinct responses for that day. Once we have the unique responses per day, we can simply increment a counter for each response.

The final step involves finding the maximum count. Since we need the lexicographically smallest response in case of ties, we compare both the count and the string value. If response A has the same count as response B, but A comes before B alphabetically (like "apple" before "banana"), we choose A.

This approach elegantly handles the duplicate removal requirement while maintaining an efficient way to track global frequency across days, making it a natural solution to the problem's constraints.

Solution Approach

The solution uses a hash table (Counter in Python) to efficiently track the occurrence count of each response across all days.

Step 1: Initialize the Counter

cnt = Counter()

We create an empty counter cnt that will store each response as a key and the number of days it appears as the value.

Step 2: Process Each Day's Responses

for ws in responses:
    for w in set(ws):
        cnt[w] += 1

For each day's responses ws:

• Convert the list to a set(ws) to automatically remove duplicates within that day
• Iterate through each unique response w in the set
• Increment the counter for that response by 1

This ensures that even if "apple" appears 3 times on day 1, it only adds 1 to cnt["apple"].

Step 3: Find the Most Common Response

ans = responses[0][0]
for w, x in cnt.items():
    if cnt[ans] < x or (cnt[ans] == x and w < ans):
        ans = w

Initialize ans with any response (here, the first response of the first day). Then iterate through all responses in the counter:

• w is the response string
• x is its count (number of days it appears)

Update ans to w if:

• cnt[ans] < x: Response w appears on more days than the current answer
• cnt[ans] == x and w < ans: Response w appears on the same number of days but is lexicographically smaller

Time Complexity: O(n * m) where n is the number of days and m is the average number of responses per day.

Space Complexity: O(k) where k is the total number of unique responses across all days.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Input: responses = [["coffee", "tea", "coffee"], ["tea", "water"], ["coffee", "water", "juice"]]

Step 1: Initialize Counter We start with an empty counter: cnt = {}

Step 2: Process Each Day

Day 0: ["coffee", "tea", "coffee"]

• Convert to set: {"coffee", "tea"} (duplicate "coffee" removed)
• Update counter:
  • cnt["coffee"] = 1
  • cnt["tea"] = 1
• Counter state: {"coffee": 1, "tea": 1}

Day 1: ["tea", "water"]

• Convert to set: {"tea", "water"} (no duplicates)
• Update counter:
  • cnt["tea"] = 2 (incremented from 1)
  • cnt["water"] = 1
• Counter state: {"coffee": 1, "tea": 2, "water": 1}

Day 2: ["coffee", "water", "juice"]

• Convert to set: {"coffee", "water", "juice"} (no duplicates)
• Update counter:
  • cnt["coffee"] = 2 (incremented from 1)
  • cnt["water"] = 2 (incremented from 1)
  • cnt["juice"] = 1
• Final counter: {"coffee": 2, "tea": 2, "water": 2, "juice": 1}

Step 3: Find Most Common Response

• Initialize: ans = "coffee" (first response of first day)
• Check each response:
  • "coffee": count = 2 (keep as current answer)
  • "tea": count = 2, same as "coffee" but "tea" > "coffee" lexicographically, no update
  • "water": count = 2, same as "coffee" but "water" > "coffee" lexicographically, no update
  • "juice": count = 1, less than 2, no update

Result: "coffee" (appears on 2 days, ties with "tea" and "water" but comes first alphabetically)

Solution Implementation

Time and Space Complexity

The time complexity is O(L), where L is the total length of all responses (i.e., the sum of lengths of all individual response lists).

Breaking down the operations:

• The outer loop iterates through all response lists: O(n) where n is the number of response lists
• For each response list, we convert it to a set and iterate through unique words: O(m_i) where m_i is the length of the i-th response list
• The set conversion for each response list takes O(m_i) time
• Adding to the counter takes O(1) per word
• The second loop iterates through all unique words in the counter: O(k) where k is the total number of unique words across all responses
• Since k ≤ L and the sum of all m_i equals L, the overall time complexity is O(L)

The space complexity is O(L), where L is the total length of all responses.

Space breakdown:

• The counter stores at most all unique words across all responses: O(k) where k ≤ L
• Creating a set for each response list uses temporary space: O(m_i) for the i-th list, but only one set exists at a time
• The maximum space used is dominated by the counter which could potentially store up to L words in the worst case (when all words are unique)
• Therefore, the space complexity is O(L)

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

Common Pitfalls

Pitfall 1: Counting Duplicates Within the Same Day

The Problem: A frequent mistake is counting duplicate responses multiple times within the same day. For instance, if day 1 has ["apple", "banana", "apple", "apple"], counting "apple" three times instead of once would give incorrect results.

Incorrect Approach:

cnt = Counter()
for ws in responses:
    for w in ws:  # Wrong: doesn't remove duplicates
        cnt[w] += 1

Correct Solution:

cnt = Counter()
for ws in responses:
    for w in set(ws):  # Correct: converts to set first
        cnt[w] += 1

Pitfall 2: Incorrect Tie-Breaking Logic

The Problem: When multiple responses have the same maximum count, the lexicographically smallest one should be returned. A common error is using the wrong comparison operator or forgetting this requirement entirely.

Incorrect Approach:

# Wrong: uses > instead of < for lexicographic comparison
if cnt[ans] < x or (cnt[ans] == x and w > ans):
    ans = w

Correct Solution:

# Correct: uses < for lexicographic comparison
if cnt[ans] < x or (cnt[ans] == x and w < ans):
    ans = w

Pitfall 3: Edge Case - Empty Response Days

The Problem: If any day has an empty response list [], the code might crash when trying to access elements or create sets.

Incorrect Handling:

ans = responses[0][0]  # Crashes if responses[0] is empty

Robust Solution:

# Handle empty responses gracefully
cnt = Counter()
for ws in responses:
    if ws:  # Check if the day has any responses
        for w in set(ws):
            cnt[w] += 1

# Initialize ans more carefully
if not cnt:
    return ""  # or handle as per requirements
ans = next(iter(cnt.keys()))  # Get any key from counter

Pitfall 4: Using Built-in Functions Incorrectly

The Problem: Using Counter.most_common() without considering the lexicographic tie-breaking requirement.

Incorrect Approach:

# Wrong: most_common() doesn't guarantee lexicographic order for ties
return cnt.most_common(1)[0][0]

Correct Solution: Either manually iterate and compare (as shown in the main solution) or sort appropriately:

# Sort by count (descending) then by word (ascending)
return max(cnt.items(), key=lambda x: (-x[1], x[0]))[0]