Find the Most Common Response - Practice Coding Problems

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 i-th 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.

Input & Output

Example 1 — Basic Deduplication and Counting

$ Input: responses = [["happy","sad","happy"],["sad","angry"]]

› Output: "sad"

💡 Note: Day 1 unique responses: {happy, sad}. Day 2 unique responses: {sad, angry}. Total counts: happy=1, sad=2, angry=1. Most frequent is 'sad' with count 2.

Example 2 — Lexicographic Tie-Breaking

$ Input: responses = [["a","b"],["b","c"]]

› Output: "a"

💡 Note: Each response appears exactly once after deduplication: a=1, b=1, c=1. All tied with frequency 1, so return lexicographically smallest: 'a'.

Example 3 — Multiple Days Same Response

$ Input: responses = [["good"],["good","bad"],["good"]]

› Output: "good"

💡 Note: After deduplication per day: Day 1: {good}, Day 2: {good, bad}, Day 3: {good}. Counts: good=3, bad=1. Most frequent is 'good'.

Constraints

1 ≤ responses.length ≤ 100
1 ≤ responses[i].length ≤ 100
1 ≤ responses[i][j].length ≤ 100
responses[i][j] consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

2D array of survey responses with duplicates within days

Deduplicate

Remove duplicates within each day using sets

Count

Count frequency of each response across all days

Output

Return most frequent response (lexicographically smallest on ties)

Key Takeaway

🎯 Key Insight: Always deduplicate within each day first, then count across all days to find the global winner

Asked in

a Amazon 35 G Google 28 M Microsoft 22 f Facebook 18

The key insight is to first remove duplicates within each day using sets, then count frequencies across all days. The optimal approach uses a hash map for O(1) frequency updates, achieving O(n) time complexity where n is the total number of responses.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Frequency Counting	O(n)	O(n)	Use hash map to efficiently count response frequencies after deduplication
Brute Force with Nested Loops	O(n²)	O(n)	Manually remove duplicates per day, then count all responses with nested loops

Hash Map Frequency Counting — Algorithm Steps

Step 1: For each day, create a set to get unique responses
Step 2: Use hash map to count frequency of each response
Step 3: Iterate through hash map to find maximum frequency
Step 4: Handle lexicographic tie-breaking

Visualization

Tap to expand

Step-by-Step Walkthrough

Deduplicate Per Day

Use sets to remove duplicates within each day

Hash Map Counting

Count frequencies using hash map

Find Winner

Select maximum frequency with lexicographic tie-breaking

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_RESPONSES 1000
#define MAX_LEN 100

typedef struct {
    char response[MAX_LEN];
    int count;
} FrequencyEntry;

char* solution(char responses[][MAX_RESPONSES][MAX_LEN], int dayCount, int* daySizes) {
    static char result[MAX_LEN];
    FrequencyEntry frequency[MAX_RESPONSES];
    int freqCount = 0;
    
    // Process each day
    for (int day = 0; day < dayCount; day++) {
        // Get unique responses for this day
        char dayUnique[MAX_RESPONSES][MAX_LEN];
        int dayUniqueCount = 0;
        
        for (int i = 0; i < daySizes[day]; i++) {
            int found = 0;
            for (int j = 0; j < dayUniqueCount; j++) {
                if (strcmp(responses[day][i], dayUnique[j]) == 0) {
                    found = 1;
                    break;
                }
            }
            if (!found) {
                strcpy(dayUnique[dayUniqueCount], responses[day][i]);
                dayUniqueCount++;
            }
        }
        
        // Count each unique response from this day
        for (int i = 0; i < dayUniqueCount; i++) {
            int found = 0;
            for (int j = 0; j < freqCount; j++) {
                if (strcmp(dayUnique[i], frequency[j].response) == 0) {
                    frequency[j].count++;
                    found = 1;
                    break;
                }
            }
            if (!found) {
                strcpy(frequency[freqCount].response, dayUnique[i]);
                frequency[freqCount].count = 1;
                freqCount++;
            }
        }
    }
    
    if (freqCount == 0) {
        strcpy(result, "");
        return result;
    }
    
    // Find maximum frequency
    int maxCount = 0;
    for (int i = 0; i < freqCount; i++) {
        if (frequency[i].count > maxCount) {
            maxCount = frequency[i].count;
        }
    }
    
    // Find lexicographically smallest among candidates
    strcpy(result, "");
    for (int i = 0; i < freqCount; i++) {
        if (frequency[i].count == maxCount) {
            if (strlen(result) == 0 || strcmp(frequency[i].response, result) < 0) {
                strcpy(result, frequency[i].response);
            }
        }
    }
    
    return result;
}

int main() {
    // Simple parsing for demo - in real implementation would need proper JSON parsing
    char responses[10][MAX_RESPONSES][MAX_LEN];
    int daySizes[10];
    int dayCount = 2;
    
    // Example input parsing
    strcpy(responses[0][0], "happy");
    strcpy(responses[0][1], "sad");
    strcpy(responses[0][2], "happy");
    daySizes[0] = 3;
    
    strcpy(responses[1][0], "sad");
    strcpy(responses[1][1], "angry");
    daySizes[1] = 2;
    
    char* result = solution(responses, dayCount, daySizes);
    printf("%s\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to remove duplicates, single pass to count, single pass to find maximum

✓ Linear Growth

Space Complexity

O(n)

Hash map stores frequency count for each unique response

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Frequency Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler