Introduction

In this blog post, we will explore how to solve the LeetCode problem "1452" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given the array favoriteCompanies where favoriteCompanies[i] is the list of favorites 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 favorites companies. You must return the indices in increasing order. Example 1: Input: favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]] Output: [0,1,4] Explanation: Person with index=2 has favoriteCompanies[2]=["google","facebook"] which is a subset of favoriteCompanies[0]=["leetcode","google","facebook"] corresponding to the person with index 0. Person with index=3 has favoriteCompanies[3]=["google"] which is a subset of favoriteCompanies[0]=["leetcode","google","facebook"] and favoriteCompanies[1]=["google","microsoft"]. Other lists of favorite companies are not a subset of another list, therefore, the answer is [0,1,4]. Example 2: Input: favoriteCompanies = [["leetcode","google","facebook"],["leetcode","amazon"],["facebook","google"]] Output: [0,1] Explanation: In this case favoriteCompanies[2]=["facebook","google"] is a subset of favoriteCompanies[0]=["leetcode","google","facebook"], therefore, the answer is [0,1]. Example 3: Input: favoriteCompanies = [["leetcode"],["google"],["facebook"],["amazon"]] Output: [0,1,2,3] Constraints: 1 <= favoriteCompanies.length <= 100 1 <= favoriteCompanies[i].length <= 500 1 <= favoriteCompanies[i][j].length <= 20 All strings in favoriteCompanies[i] are distinct. All lists of favorite companies are distinct, that is, If we sort alphabetically each list then favoriteCompanies[i] != favoriteCompanies[j]. All strings consist of lowercase English letters only.

Explanation

Here's the breakdown of the solution:

• Sort Company Lists: Sort each person's list of favorite companies alphabetically. This enables efficient subset checking using a linear scan.
• Subset Check: For each person's list, iterate through all other lists and check if the current list is a subset of any other list.

• Result: If a person's list is not a subset of any other list, add their index to the result. Finally, return the sorted list of indices.

• Runtime Complexity: O(n² * m), where n is the number of people (length of favoriteCompanies) and m is the maximum length of a company list.

• Storage Complexity: O(n * m), primarily for storing the sorted company lists.

Code

    def people_indexes(favoriteCompanies):
    """
    Finds the indices of people whose list of favorite companies is not a subset of any other list.

    Args:
        favoriteCompanies: A list of lists, where each inner list represents the favorite companies of a person.

    Returns:
        A list of indices, in increasing order, of people whose favorite companies are not a subset of any other list.
    """
    n = len(favoriteCompanies)
    sorted_companies = []
    for companies in favoriteCompanies:
        companies.sort()
        sorted_companies.append(companies)

    result = []
    for i in range(n):
        is_subset = False
        for j in range(n):
            if i != j:
                if is_subset_list(sorted_companies[i], sorted_companies[j]):
                    is_subset = True
                    break
        if not is_subset:
            result.append(i)

    return result

def is_subset_list(list1, list2):
    """
    Checks if list1 is a subset of list2.

    Args:
        list1: The potential subset list.
        list2: The potential superset list.

    Returns:
        True if list1 is a subset of list2, False otherwise.
    """
    i = 0
    j = 0
    while i < len(list1) and j < len(list2):
        if list1[i] == list2[j]:
            i += 1
            j += 1
        elif list1[i] < list2[j]:
            return False  # list1[i] not found in list2
        else:
            j += 1
    return i == len(list1)  # True if all elements of list1 were found in list2