Welcome to Subscribe On Youtube

2248. Intersection of Multiple Arrays

Description

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

 

Example 1:

Input: nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]
Output: [3,4]
Explanation: 
The only integers present in each of nums[0] = [3,1,2,4,5], nums[1] = [1,2,3,4], and nums[2] = [3,4,5,6] are 3 and 4, so we return [3,4].

Example 2:

Input: nums = [[1,2,3],[4,5,6]]
Output: []
Explanation: 
There does not exist any integer present both in nums[0] and nums[1], so we return an empty list [].

 

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= sum(nums[i].length) <= 1000
  • 1 <= nums[i][j] <= 1000
  • All the values of nums[i] are unique.

Solutions

Code Walkthrough

  1. Initialization: A counter array cnt of size 1001 is initialized with zeros. The size 1001 is chosen to accommodate the elements in the range [0, 1000], assuming the problem constraints specify that elements will fall within this range.

  2. Counting Elements:
    • The code iterates through each array arr in the list of lists nums.
    • For every element x in each array, the code increments the count of that element in the cnt array by 1. This process effectively counts the occurrences of each element across all arrays.
  3. Finding the Intersection:
    • The code then constructs a list comprehension that iterates over the cnt array. For each element x (which is the index representing the actual number) and its corresponding value v (which is the count of how many times that number appeared across all arrays), it checks if v is equal to the length of the list of lists nums.
    • This condition (v == len(nums)) ensures that the element represented by x appears in every array, as its count matches the total number of arrays.
    • The list comprehension returns a list of such elements x that satisfy this condition, effectively representing the intersection of all arrays.

Example

Consider nums = [[1, 2, 3], [4, 5, 1], [1, 10, 15, 20]]:

  • The element 1 appears in all three arrays, so its count in cnt[1] will be 3 after iterating through all arrays.
  • No other elements appear in all three arrays, so their counts in cnt will be less than 3.
  • The method intersection returns [1], as 1 is the only element common to all arrays.
  • class Solution {
        public List<Integer> intersection(int[][] nums) {
            int[] cnt = new int[1001];
            for (var arr : nums) {
                for (int x : arr) {
                    ++cnt[x];
                }
            }
            List<Integer> ans = new ArrayList<>();
            for (int x = 0; x < 1001; ++x) {
                if (cnt[x] == nums.length) {
                    ans.add(x);
                }
            }
            return ans;
        }
    }
    
  • class Solution {
    public:
        vector<int> intersection(vector<vector<int>>& nums) {
            int cnt[1001]{};
            for (auto& arr : nums) {
                for (int& x : arr) {
                    ++cnt[x];
                }
            }
            vector<int> ans;
            for (int x = 0; x < 1001; ++x) {
                if (cnt[x] == nums.size()) {
                    ans.push_back(x);
                }
            }
            return ans;
        }
    };
    
  • class Solution:
        def intersection(self, nums: List[List[int]]) -> List[int]:
            cnt = [0] * 1001
            for arr in nums:
                for x in arr:
                    cnt[x] += 1
            return [x for x, v in enumerate(cnt) if v == len(nums)]
    
    
  • func intersection(nums [][]int) (ans []int) {
    	cnt := [1001]int{}
    	for _, arr := range nums {
    		for _, x := range arr {
    			cnt[x]++
    		}
    	}
    	for x, v := range cnt {
    		if v == len(nums) {
    			ans = append(ans, x)
    		}
    	}
    	return
    }
    
  • function intersection(nums: number[][]): number[] {
        const cnt = new Array(1001).fill(0);
        for (const arr of nums) {
            for (const x of arr) {
                cnt[x]++;
            }
        }
        const ans: number[] = [];
        for (let x = 0; x < 1001; x++) {
            if (cnt[x] === nums.length) {
                ans.push(x);
            }
        }
        return ans;
    }
    
    
  • class Solution {
        /**
         * @param Integer[][] $nums
         * @return Integer[]
         */
        function intersection($nums) {
            $rs = [];
            for ($i = 0; $i < count($nums); $i++) {
                for ($j = 0; $j < count($nums[$i]); $j++) {
                    $hashtable[$nums[$i][$j]] += 1;
                    if ($hashtable[$nums[$i][$j]] === count($nums)) {
                        array_push($rs, $nums[$i][$j]);
                    }
                }
            }
            sort($rs);
            return $rs;
        }
    }
    
    

All Problems

All Solutions