algoadvance

Leetcode 2032. Two Out of Three

Problem Statement

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 arrays contain duplicate values?
    • Yes, the arrays can contain duplicate values, but we are interested only in distinct numbers that appear in at least two of the three arrays.
  2. What is the size range for each of the input arrays?
    • The input arrays can have any size ranging from 0 to 100.
  3. Can the input arrays be empty?
    • Yes, the inputs can be empty.
  4. What should be the output if all input arrays are empty?
    • The output should be an empty array.

Strategy

  1. Use Sets for Uniqueness:
    • Convert each of the three input arrays into sets to remove duplicates within individual arrays.
  2. Count Occurrences:
    • Use a Map (specifically a HashMap) to count the occurrences of each number across the three sets.
  3. Collect Results:
    • Iterate through the map to find numbers that appear in at least two out of the three sets and collect these numbers into a result list.
  4. Return Result:
    • Convert the result list into an array and return it.

Code

import java.util.*;

public class Solution {
    public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
        // Create sets to remove duplicates within the same array
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        Set<Integer> set3 = new HashSet<>();
        
        for (int num : nums1) set1.add(num);
        for (int num : nums2) set2.add(num);
        for (int num : nums3) set3.add(num);
        
        // Use a map to count occurrences across sets
        Map<Integer, Integer> countMap = new HashMap<>();
        
        // Helper method to count occurrences
        addToMap(set1, countMap);
        addToMap(set2, countMap);
        addToMap(set3, countMap);
        
        // Prepare the result list
        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            if (entry.getValue() >= 2) {
                result.add(entry.getKey());
            }
        }
        
        return result;
    }
    
    private void addToMap(Set<Integer> set, Map<Integer, Integer> map) {
        for (int num : set) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
    }
}

Time Complexity

Overall, the time complexity is O(n + m + p), which is linear with respect to the total number of elements in the input arrays.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI