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 <= 1001 <= nums1[i], nums2[j], nums3[k] <= 100To solve the problem, we'll use sets to capture unique elements from each array, then count the total appearances of each element across all arrays. Finally, we'll select elements that appear in at least two arrays.
The approach involves converting each array into a set to fetch distinct elements. We then use a dictionary (or map) to track the frequency of each element appearing across the three sets.
The function twoOutOfThree creates sets for each input list to get unique values from them. It uses a dictionary to count how many sets each element appears in. Finally, it returns a list of elements that appear in at least two sets.
Java
C
JavaScript
C#
C++
Time Complexity: O(n), where n is the total number of elements across all input lists since we iterate through each element once.
Space Complexity: O(u), where u is the number of unique elements given the constraints.
This method employs auxiliary arrays to record the presence frequency of elements. Given the constraint that elements are between 1 and 100, we can use a fixed-size frequency array to track how many of the three arrays contain any given element.
This Python solution uses a frequency array of size 101 to count how many times a number is present in the three arrays. By marking the frequency for unique elements in each list, the solution considers elements appearing in at least two arrays.
Java
JavaScript
C#
C++
Time Complexity: O(n), where n is the sum of lengths of nums1, nums2, and nums3.
Space Complexity: O(100), which is effectively O(1).
| Approach | Complexity |
|---|---|
| Using Sets to Store Unique Elements and Count Occurrences | Time Complexity: |
| Using Frequency Arrays | Time Complexity: |
3Sum - Leetcode 15 - Python • NeetCode • 980,205 views views
Watch 9 more video solutions →Practice Two Out of Three with our built-in code editor and test cases.
Practice on FleetCode