Leetcode – Two Out of Three Solution

Spread the love

“Two Out of Three” is an engaging problem on Leetcode that challenges your array manipulation and hashing skills. While the problem’s central idea might seem intuitive, various subtleties can be explored for optimal solutions. This article will provide an in-depth examination of the problem, its constraints, different methods to tackle it, and a deep dive into their respective time complexities.

1. Problem Statement

You are given three integer arrays nums1, nums2, and nums3. You aim to return a sorted list of all distinct integers that appear in at least two out of the three arrays.

Example:

Input: nums1 = [1,1,3,2], nums2 = [2,3,4], nums3 = [5,6,2,2]

Output: [2,3]

2. Assumptions and Constraints

  • All the input arrays will have a length of between 1 and 100.
  • Each array may contain duplicates.
  • Each array’s elements are integers ranging from 1 to 100.

3. Solution Approaches

A. Brute Force Method

The simplest approach is to check each unique number from one array in the other two arrays. If found, you add it to the result list.

B. Hashing and Set Operations

This method takes advantage of Python’s powerful set operations:

  1. Convert each list into a set to get unique values.
  2. Find numbers that appear in at least two arrays using set unions and intersections.
  3. Return the sorted result.

Python Code:

def twoOutOfThree(nums1, nums2, nums3):
    set1, set2, set3 = set(nums1), set(nums2), set(nums3)
    
    # Finding common numbers between the sets
    result = set1 & set2 | set2 & set3 | set1 & set3
    
    return sorted(result)

4. Time Complexity Analysis

  • Brute Force Method: The worst-case scenario would be O(n^3) where n is the maximum size among the three arrays.
  • Hashing and Set Operations: The time complexity is O(n) for converting arrays to sets and O(1) average time for set operations. However, the sorting step makes it O(n log⁡ n).

5. Conclusion

The “Two Out of Three” problem on Leetcode is a perfect exercise for understanding array manipulations and the power of hashing in Python. While a brute force approach might seem straightforward, an optimized solution using sets significantly reduces the time complexity.

Leave a Reply