Scale Engineer

Intersection of Multiple Arrays

Easy
#2048Time: 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: 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.
Patterns
Counting
Algorithms
Sorting
Data structures
ArrayHash Table

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem