Intersection of Multiple Arrays

EASY

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.

Approaches

Checkout 3 different approaches to solve Intersection of Multiple Arrays. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Nested Loops

This approach iterates through each element of the first array and checks if it is present in all the other subsequent arrays. If an element is found in every array, it's added to the result list.

Algorithm

Initialize an empty list result.
For each candidate in the first array nums[0]:
- Set a boolean flag isPresentInAll to true.
- For each subsequent array nums[i] (from i=1 to nums.length - 1):
  - Linearly scan nums[i] to check for candidate.
  - If candidate is not found, set isPresentInAll to false and break the inner loop.
- If isPresentInAll is still true after checking all arrays, add candidate to result.
Sort the result list.
Return result.

We start by considering the first array nums[0] as a base for potential candidates for the intersection. We iterate through each number candidate in nums[0]. For each candidate, we then check its presence in all the other arrays from nums[1] to nums[nums.length - 1]. A flag, say isPresentInAll, is used to track if the candidate is found in every array. To check if candidate is in nums[i], we perform a linear scan through nums[i]. If it's not found, we set the flag to false and can immediately stop checking for this candidate in further arrays. If the flag remains true after checking all arrays, the candidate is added to our result list. Finally, the result list is sorted in ascending order as required.

import java.util.*;

class Solution {
    public List<Integer> intersection(int[][] nums) {
        if (nums == null || nums.length == 0) {
            return new ArrayList<>();
        }

        List<Integer> result = new ArrayList<>();
        // Iterate through each number in the first array
        for (int candidate : nums[0]) {
            boolean isPresentInAll = true;
            // Check against all other arrays
            for (int i = 1; i < nums.length; i++) {
                boolean foundInCurrentArray = false;
                // Linear scan to find the candidate in the current array
                for (int num : nums[i]) {
                    if (num == candidate) {
                        foundInCurrentArray = true;
                        break;
                    }
                }
                if (!foundInCurrentArray) {
                    isPresentInAll = false;
                    break;
                }
            }
            if (isPresentInAll) {
                result.add(candidate);
            }
        }
        Collections.sort(result);
        return result;
    }
}

Complexity Analysis

Time Complexity: O(L_0 * S), where `L_0` is the length of the first array and `S` is the total number of elements in `nums`. For each of the `L_0` elements, we might scan through almost all other `S - L_0` elements. Sorting adds an additional `O(k log k)` complexity.Space Complexity: O(k), where `k` is the number of elements in the intersection. This space is used for the result list. In the worst case, `k` can be up to the length of the smallest array.

Pros and Cons

Pros:

Simple to understand and implement without complex data structures.

Cons:

Highly inefficient, especially if the arrays are large.
The time complexity is poor due to multiple nested loops and repeated linear scans.

Code Solutions

Checking out 3 solutions in different languages for Intersection of Multiple Arrays. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Intersection of Multiple Arrays

Algorithms:

Sorting

Patterns:

Counting

Data Structures:

ArrayHash Table