People Whose List of Favorite Companies Is Not a Subset of Another List - Problem

Given the array favoriteCompanies where favoriteCompanies[i] is the list of favorite companies for the ith person (indexed from 0).

Return the indices of people whose list of favorite companies is not a subset of any other list of favorite companies. You must return the indices in increasing order.

A subset means that all elements of list A appear in list B, but B can have additional elements.

Input & Output

Example 1 — Basic Case

$ Input: favoriteCompanies = [["leetcode","google","facebook"],["leetcode","microsoft"],["google","microsoft"]]

› Output: [0,1,2]

💡 Note: Person 0 ["leetcode","google","facebook"] is not a subset of any other list. Person 1 ["leetcode","microsoft"] is not a subset of any other list (person 0 is missing "microsoft", person 2 is missing "leetcode"). Person 2 ["google","microsoft"] is not a subset of any other list. So all indices [0,1,2] are returned.

Example 2 — No Subsets

$ Input: favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["facebook","linkedin"]]

› Output: [0,1,2]

💡 Note: No person's list is a complete subset of another person's list, so all indices are returned

Example 3 — Multiple Subsets

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

› Output: [3]

💡 Note: Person 0 ["a","b"] ⊆ Person 3 ["a","b","c"], Person 1 ["a"] ⊆ multiple others, Person 2 ["b"] ⊆ multiple others. Only Person 3 is not a subset of anyone.

Constraints

1 ≤ favoriteCompanies.length ≤ 100
1 ≤ favoriteCompanies[i].length ≤ 500
1 ≤ favoriteCompanies[i][j].length ≤ 20
All strings in favoriteCompanies[i] are distinct
All the strings of favoriteCompanies are distinct

Visualization

Tap to expand

Asked in

a Amazon 15 G Google 12

The key insight is to check if each person's favorite companies list is a subset of any other person's list. Best approach uses hash sets for O(1) company lookups during subset checking. Time: O(n²m), Space: O(nm)

Common Approaches

✓ Brute Force with Lists

⏱️ Time: O(n²m²) Space: O(1)

Compare each person's favorite companies against every other person's list. For each comparison, check if all companies in the first list exist in the second list using linear search.

Hash Set Optimization

⏱️ Time: O(n²m) Space: O(nm)

First convert all company lists to hash sets for constant-time lookups. Then for each person, check if their companies are a subset of any other person's companies using set operations.

Brute Force with Lists — Algorithm Steps

For each person i
Compare against every other person j
Check if all companies of i exist in j's list
If not a subset of any other list, add i to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare Person 0

Check if ["leetcode","google","facebook"] ⊆ others

Compare Person 1

Check if ["leetcode","microsoft"] ⊆ others

Find Non-subsets

Person 1's list is subset of Person 0, so return [0,2]

Code -

solution.c — C

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

#define MAX_PEOPLE 100
#define MAX_COMPANIES 500
#define MAX_NAME_LEN 50

static char companies[MAX_PEOPLE][MAX_COMPANIES][MAX_NAME_LEN];
static int companyCounts[MAX_PEOPLE];
static int result[MAX_PEOPLE];
static char line[10000];

int solution(int n) {
    int resultCount = 0;
    
    for (int i = 0; i < n; i++) {
        int isSubset = 0;
        
        for (int j = 0; j < n; j++) {
            if (i != j) {
                // Check if companies[i] is subset of companies[j]
                int allFound = 1;
                for (int k = 0; k < companyCounts[i]; k++) {
                    int found = 0;
                    for (int l = 0; l < companyCounts[j]; l++) {
                        if (strcmp(companies[i][k], companies[j][l]) == 0) {
                            found = 1;
                            break;
                        }
                    }
                    if (!found) {
                        allFound = 0;
                        break;
                    }
                }
                
                if (allFound) {
                    isSubset = 1;
                    break;
                }
            }
        }
        
        if (!isSubset) {
            result[resultCount++] = i;
        }
    }
    
    return resultCount;
}

int main() {
    fgets(line, sizeof(line), stdin);
    
    int n = 0;
    int i = 1; // skip first '['
    
    while (i < strlen(line) - 1) {
        if (line[i] == '[') {
            companyCounts[n] = 0;
            i++; // skip '['
            char current[MAX_NAME_LEN] = "";
            int currentLen = 0;
            int inQuotes = 0;
            
            while (i < strlen(line) && !(line[i] == ']' && !inQuotes)) {
                char c = line[i];
                if (c == '"') {
                    inQuotes = !inQuotes;
                } else if (c == ',' && !inQuotes) {
                    if (currentLen > 0) {
                        current[currentLen] = '\0';
                        strcpy(companies[n][companyCounts[n]], current);
                        companyCounts[n]++;
                        currentLen = 0;
                    }
                } else if (inQuotes) {
                    current[currentLen++] = c;
                }
                i++;
            }
            
            if (currentLen > 0) {
                current[currentLen] = '\0';
                strcpy(companies[n][companyCounts[n]], current);
                companyCounts[n]++;
            }
            
            n++;
            i++; // skip ']'
            
            // Skip comma if present
            if (i < strlen(line) && line[i] == ',') {
                i++;
            }
        } else {
            i++;
        }
    }
    
    int resultCount = solution(n);
    
    printf("[");
    for (int j = 0; j < resultCount; j++) {
        if (j > 0) printf(",");
        printf("%d", result[j]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²m²)

n people compared pairwise, each comparison checks m companies against m companies

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

18.5K Views

Medium Frequency

~25 min Avg. Time

342 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

People Whose List of Favorite Companies Is Not a Subset of Another List - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Lists — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler