Problem Statement in English

You’re given a list of lists of strings, where each list represents the responses of a group of people on a particular day.

Your task is to find the most common response across all days. If there are multiple responses with the same frequency, return the lexicographically smallest one.

Approach

There’s no real twists to this quesiton. We can use a hashmap to count the frequency of each response across all days. We can also use a set to keep track of the responses we’ve already counted for each day, to avoid double counting. We can then iterate through the hashmap to find the response with the highest frequency. If there are multiple responses with the same frequency, we can use the min function to find the lexicographically smallest one.

Solution in Python


class Solution:
    def findCommonResponse(self, responses: List[List[str]]) -> str:
        res, freq = "", 0

        hm = defaultdict(int)

        for day in responses:
            seen = set()

            for response in day:
                if response not in seen:
                    seen.add(response)
                    hm[response] += 1

                    if hm[response] > freq:
                        res = response
                        freq = hm[response]
                    elif hm[response] == freq and response < res:
                        res = response

        return res

Complexity

  • Time: $O(n)$
    Where n is the total number of responses across all days. We iterate through each response once to count the frequency and then iterate through the hashmap to find the most common response.

  • Space: $O(n)$
    Since we are using a hashmap to store the frequency of each response, the space complexity is $O(n)$.

And we are done.