algoadvance

Leetcode 2248. Intersection of Multiple Arrays

Problem Statement

Given a 2D integer array nums where nums[i] is a list of integers, return a list of integers that are present in each array of nums sorted in ascending order.

Example:

Input: nums = [[3,1,2,4,5], [1,2,3,4], [3,4,5,6,7]]
Output: [3, 4]

Clarifying Questions

1. Can the input lists contain duplicate integers?
   • Yes, but for the purpose of the intersection, duplicates within the same list do not affect the result.
2. What should be returned if there are no common elements?
   • Return an empty list.
3. How large can the input arrays be?
   • The constraints need to be considered, but typically, each individual list’s length and the number of lists should be reasonably large but manageable within efficiency constraints.

Strategy

1. Create a Count Map:
   • Traverse through each number in every array and count its occurrences across all arrays using a hash map.
2. Filter Common Elements:
   • Filter numbers which appear in all subarrays using the constructed map. These are elements whose count matches the number of arrays.
3. Sorting:
   • Sort the filtered elements before returning them.

Detailed Steps

1. Initialize an empty hash map to count occurrences of each integer.
2. Traverse each integer in every subarray and update the count in the hash map.
3. Filter the integers that have a count equal to the total number of subarrays.
4. Sort and return the resulting list of common integers.

Code

#include <vector>
#include <unordered_map>
#include <algorithm>

std::vector<int> intersectionOfArrays(const std::vector<std::vector<int>>& nums) {
    std::unordered_map<int, int> countMap;
    int listCount = nums.size();

    // Count the occurrence of each integer across all subarrays
    for (const auto& sublist : nums) {
        for (int num : sublist) {
            countMap[num]++;
        }
    }

    std::vector<int> result;
    
    // Collect integers that appear in all subarrays
    for (const auto& entry : countMap) {
        if (entry.second == listCount) {
            result.push_back(entry.first);
        }
    }

    // Sort the result in ascending order
    std::sort(result.begin(), result.end());
    return result;
}

Time Complexity

• Counting step: O(n*m), where n is the number of subarrays and m is the average length of the subarrays.
• Filtering step: O(k), where k is the number of unique integers counted.
• Sorting step: O(k log k), where k is the number of common integers.
• Overall complexity: The dominant factor is O(n*m + k log k), usually dominated by the counting and sorting operations.

This approach ensures a clear and efficient way to find the intersection of numbers present in every array, while also considering the sorting of the resultant intersection.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?