Jobs

Interviews

Discussions

Two Out of Three

Easy

Booking.com

0 views

Topics:

ArraysHash Table

Given three integer arrays nums1, nums2, and nums3, return a distinct array containing all the values that are present in at least two out of the three arrays. You may return the values in any order.

Example 1:

Input: nums1 = [1,1,3,2], nums2 = [2,3], nums3 = [3]
Output: [3,2]
Explanation: The values that are present in at least two arrays are:
- 3, in all three arrays.
- 2, in nums1 and nums2.

Example 2:

Input: nums1 = [3,1], nums2 = [2,3], nums3 = [1,2]
Output: [2,3,1]
Explanation: The values that are present in at least two arrays are:
- 2, in nums2 and nums3.
- 3, in nums1 and nums2.
- 1, in nums1 and nums3.

Example 3:

Input: nums1 = [1,2,2], nums2 = [4,3,3], nums3 = [5]
Output: []
Explanation: No value is present in at least two arrays.

Constraints:

1 <= nums1.length, nums2.length, nums3.length <= 100
1 <= nums1[i], nums2[j], nums3[k] <= 100

Try coding it in LeetCode

Two Out of Three

Easy

Booking.com

0 views

Topics:

ArraysHash Table

Example 1:

Input: nums1 = [1,1,3,2], nums2 = [2,3], nums3 = [3]
Output: [3,2]
Explanation: The values that are present in at least two arrays are:
- 3, in all three arrays.
- 2, in nums1 and nums2.

Example 2:

Input: nums1 = [3,1], nums2 = [2,3], nums3 = [1,2]
Output: [2,3,1]
Explanation: The values that are present in at least two arrays are:
- 2, in nums2 and nums3.
- 3, in nums1 and nums2.
- 1, in nums1 and nums3.

Example 3:

Input: nums1 = [1,2,2], nums2 = [4,3,3], nums3 = [5]
Output: []
Explanation: No value is present in at least two arrays.

Constraints:

1 <= nums1.length, nums2.length, nums3.length <= 100
1 <= nums1[i], nums2[j], nums3[k] <= 100

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input arrays contain negative numbers, zeros, or duplicates?
What is the expected size range for the input arrays? Should I be concerned about memory usage with very large inputs?
If a number appears in all three arrays, should it be included in the result only once, or multiple times?
What data type should the output be? Specifically, should it be a list of integers, or something else (e.g., a set)?
If an element appears in only one array, or none, should it be ignored?

Brute Force Solution

Approach

The brute force strategy for finding numbers that appear in at least two out of three lists is to examine every possible number in each list and compare them across all the lists. This involves checking each number to see if it exists in at least two lists.

Here's how the algorithm would work step-by-step:

Take the first list and consider each number in that list individually.
For each number in the first list, check if it exists in the second list. If it does, mark it as found in two lists.
For that same number from the first list, also check if it exists in the third list. If it does, mark it as found in two lists (if not already) or in three lists.
Repeat this process for every number in the first list.
Now, repeat steps 1-4 for the second list, comparing each of its numbers to the first and third lists.
Finally, repeat steps 1-4 for the third list, comparing each of its numbers to the first and second lists.
Collect all the numbers that were marked as appearing in at least two lists. Make sure to remove any duplicates from this collection.

Code Implementation

def twoOutOfThree(first_list, second_list, third_list):
    result = set()

    # Iterate through the first list
    for number_from_first_list in first_list:
        count = 0
        if number_from_first_list in second_list:
            count += 1

        if number_from_first_list in third_list:
            count += 1

        if count >= 1:
            result.add(number_from_first_list)

    # Iterate through the second list
    for number_from_second_list in second_list:
        count = 0

        # Ensures we account for items in at least two lists
        if number_from_second_list in first_list:
            count += 1

        if number_from_second_list in third_list:
            count += 1

        if count >= 1:
            result.add(number_from_second_list)

    # Iterate through the third list
    for number_from_third_list in third_list:
        count = 0

        if number_from_third_list in first_list:
            count += 1

        if number_from_third_list in second_list:
            count += 1

        # Add the number to the result if it's in at least two lists
        if count >= 1:
            result.add(number_from_third_list)

    numbers_in_at_least_two_lists = []
    for number in result:
        first_count = first_list.count(number)
        second_count = second_list.count(number)
        third_count = third_list.count(number)
        if (first_count > 0 and second_count > 0) or \
           (first_count > 0 and third_count > 0) or \
           (second_count > 0 and third_count > 0):
            numbers_in_at_least_two_lists.append(number)

    return numbers_in_at_least_two_lists

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm iterates through each of the three input lists. Assume that each list has a maximum size of 'n'. For each element in one list, it checks for its existence in the other two lists. This check involves iterating through the other lists, which takes O(n) time in the worst case. Since this process is repeated for each element in each of the three lists, the overall time complexity is approximately 3 * n * (2 * n). This simplifies to O(n^2) after removing constant factors. The dominant factor driving the cost is the nested iterations required to compare elements across lists.

Space Complexity

O(N) – The brute force approach described utilizes a data structure, likely a set or a list, to store the numbers found in at least two of the input lists. The maximum size of this data structure would be proportional to the total number of unique elements across all three lists. Let N be the total number of elements across all lists; in the worst-case scenario where all elements are unique and appear in at least two lists, the space used by the auxiliary data structure will be proportional to N. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The goal is to identify numbers that appear in at least two of the given three lists. We can achieve this efficiently by tracking which lists each number appears in, and then checking if any number meets the requirement.

Here's how the algorithm would work step-by-step:

Create a system to remember which of the three lists each number is found in.
Go through the first list, and for each number, mark that it's present in the first list.
Repeat this process for the second and third lists, marking the presence of each number in the corresponding list.
Now, examine the records we've created. For each number, see how many different lists it appears in.
If a number is found in at least two lists, add it to our final result.
Finally, present the list of numbers that appear in at least two of the original lists, removing duplicates.

Code Implementation

def two_out_of_three(nums1, nums2, nums3):
    list_appearances = {}

    # Track appearance of numbers in the first list.
    for number in nums1:
        if number not in list_appearances:
            list_appearances[number] = [1, 0, 0]
        else:
            list_appearances[number][0] = 1

    # Track appearance of numbers in the second list.
    for number in nums2:
        if number not in list_appearances:
            list_appearances[number] = [0, 1, 0]
        else:
            list_appearances[number][1] = 1

    # Track appearance of numbers in the third list.
    for number in nums3:
        if number not in list_appearances:
            list_appearances[number] = [0, 0, 1]
        else:
            list_appearances[number][2] = 1

    result = []
    # Identify numbers present in at least two lists.
    for number, appearance in list_appearances.items():

        if sum(appearance) >= 2:
            result.append(number)

    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each of the three input lists once, where n is the total number of elements across all three lists. Recording the presence of each number in each list takes constant time per element. After processing all lists, it iterates through the unique numbers encountered, which is at most the total number of elements. Checking the list presence for each unique number also takes constant time. Therefore, the dominant factor is the initial iteration through the lists, making the time complexity O(n).

Space Complexity

O(N) – The algorithm uses a system to remember which of the three lists each number is found in. This implies a data structure, likely a hash map or set, to store each unique number and the lists it appears in. In the worst case, all numbers across the three lists are unique, leading to a space usage proportional to the total number of elements across all three lists, where N represents the total number of elements. Additionally, space is used to store the final result list, which in the worst case, can also contain a number of elements proportional to N. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input arrays	Return an empty list if any of the input arrays are null or empty.
Arrays with duplicate numbers within each array	Use sets to remove duplicates within each array before processing.
Large input arrays that could cause memory issues	Use efficient data structures like sets and minimize memory usage.
Integer overflow when calculating frequency counts	Employ appropriate data types like long to prevent integer overflow.
All three arrays are identical	The set operations will still function correctly, yielding elements present in at least two.
One array contains all elements from the other two	The set operations correctly identify elements present in at least two arrays.
Arrays containing negative numbers	The solution should handle negative numbers correctly as hashset do support negative values.
Arrays containing zero	The solution should handle zero correctly as hashset do support zero value.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input arrays contain negative numbers, zeros, or duplicates?
What is the expected size range for the input arrays? Should I be concerned about memory usage with very large inputs?
If a number appears in all three arrays, should it be included in the result only once, or multiple times?
What data type should the output be? Specifically, should it be a list of integers, or something else (e.g., a set)?
If an element appears in only one array, or none, should it be ignored?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first list and consider each number in that list individually.
For each number in the first list, check if it exists in the second list. If it does, mark it as found in two lists.
For that same number from the first list, also check if it exists in the third list. If it does, mark it as found in two lists (if not already) or in three lists.
Repeat this process for every number in the first list.
Now, repeat steps 1-4 for the second list, comparing each of its numbers to the first and third lists.
Finally, repeat steps 1-4 for the third list, comparing each of its numbers to the first and second lists.
Collect all the numbers that were marked as appearing in at least two lists. Make sure to remove any duplicates from this collection.

Code Implementation

def twoOutOfThree(first_list, second_list, third_list):
    result = set()

    # Iterate through the first list
    for number_from_first_list in first_list:
        count = 0
        if number_from_first_list in second_list:
            count += 1

        if number_from_first_list in third_list:
            count += 1

        if count >= 1:
            result.add(number_from_first_list)

    # Iterate through the second list
    for number_from_second_list in second_list:
        count = 0

        # Ensures we account for items in at least two lists
        if number_from_second_list in first_list:
            count += 1

        if number_from_second_list in third_list:
            count += 1

        if count >= 1:
            result.add(number_from_second_list)

    # Iterate through the third list
    for number_from_third_list in third_list:
        count = 0

        if number_from_third_list in first_list:
            count += 1

        if number_from_third_list in second_list:
            count += 1

        # Add the number to the result if it's in at least two lists
        if count >= 1:
            result.add(number_from_third_list)

    numbers_in_at_least_two_lists = []
    for number in result:
        first_count = first_list.count(number)
        second_count = second_list.count(number)
        third_count = third_list.count(number)
        if (first_count > 0 and second_count > 0) or \
           (first_count > 0 and third_count > 0) or \
           (second_count > 0 and third_count > 0):
            numbers_in_at_least_two_lists.append(number)

    return numbers_in_at_least_two_lists

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Create a system to remember which of the three lists each number is found in.
Go through the first list, and for each number, mark that it's present in the first list.
Repeat this process for the second and third lists, marking the presence of each number in the corresponding list.
Now, examine the records we've created. For each number, see how many different lists it appears in.
If a number is found in at least two lists, add it to our final result.
Finally, present the list of numbers that appear in at least two of the original lists, removing duplicates.

Code Implementation

def two_out_of_three(nums1, nums2, nums3):
    list_appearances = {}

    # Track appearance of numbers in the first list.
    for number in nums1:
        if number not in list_appearances:
            list_appearances[number] = [1, 0, 0]
        else:
            list_appearances[number][0] = 1

    # Track appearance of numbers in the second list.
    for number in nums2:
        if number not in list_appearances:
            list_appearances[number] = [0, 1, 0]
        else:
            list_appearances[number][1] = 1

    # Track appearance of numbers in the third list.
    for number in nums3:
        if number not in list_appearances:
            list_appearances[number] = [0, 0, 1]
        else:
            list_appearances[number][2] = 1

    result = []
    # Identify numbers present in at least two lists.
    for number, appearance in list_appearances.items():

        if sum(appearance) >= 2:
            result.append(number)

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input arrays	Return an empty list if any of the input arrays are null or empty.
Arrays with duplicate numbers within each array	Use sets to remove duplicates within each array before processing.
Large input arrays that could cause memory issues	Use efficient data structures like sets and minimize memory usage.
Integer overflow when calculating frequency counts	Employ appropriate data types like long to prevent integer overflow.
All three arrays are identical	The set operations will still function correctly, yielding elements present in at least two.
One array contains all elements from the other two	The set operations correctly identify elements present in at least two arrays.
Arrays containing negative numbers	The solution should handle negative numbers correctly as hashset do support negative values.
Arrays containing zero	The solution should handle zero correctly as hashset do support zero value.