algoadvance

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 result in any order.

Clarifying Questions

  1. Can the input arrays contain duplicate values?
    • Yes, the input arrays can contain duplicate values, but a value should only appear once in the output if it is present in at least two arrays.
  2. Is there a limit on the size of the input arrays?
    • Although leetcode problems usually do not specify size limits for input arrays, let’s assume they are within a reasonable size to fit into memory (usually up to 10^4 elements).
  3. Should the output array be sorted?
    • The problem does not specify that the output needs to be sorted. Return the result in any order.

Strategy

  1. Use Sets for Uniqueness: Convert each of the input arrays into sets to remove duplicates within each individual array.
  2. Count Occurrences Across Arrays: Use a dictionary to count how many of the given arrays each number appears in.
  3. Filter the Results: Add numbers that appear in at least two of the three arrays to the result list.
  4. Return the Result: Convert the resulting set back to a list and return it.

Code

from collections import defaultdict

def twoOutOfThree(nums1, nums2, nums3):
    # Convert each list to a set to remove duplicates
    set1, set2, set3 = set(nums1), set(nums2), set(nums3)
    
    # Dictionary to keep track of the appearance count
    appearance_count = defaultdict(int)
    
    # Function to update the count dictionary
    def update_count(num_set):
        for num in num_set:
            appearance_count[num] += 1
            
    update_count(set1)
    update_count(set2)
    update_count(set3)
    
    # Collect numbers that appear in at least two sets
    result = [num for num, count in appearance_count.items() if count > 1]
    
    return result
    
# Example usage:
nums1 = [1, 1, 3, 2]
nums2 = [2, 3]
nums3 = [3]
print(twoOutOfThree(nums1, nums2, nums3))  # Output: [2, 3]

Time Complexity

  1. Set Conversion: Converting each list of size n into a set takes O(n). Since we have three lists, this step takes O(n + m + o) where n, m, and o are lengths of nums1, nums2, and nums3 respectively.
  2. Counting Occurrences: Iterating over each of the sets takes O(n) for each set, so O(n + m + o) in total.
  3. Filtering Results: This involves a single pass over the dictionary, which contains at most n + m + o entries, thus taking O(n + m + o).

Overall, the time complexity is O(n + m + o), which is efficient for this problem.

Space Complexity

The space complexity is mainly from:

So, the space complexity is O(n + m + o).

Try our interview co-pilot at AlgoAdvance.com