LeetCode 2248 - Intersection of Multiple Arrays

LeetCode Problem 2248

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Sorting, Counting

Solution

Problem Understanding

The problem is asking us to find the intersection of multiple arrays. Specifically, given a 2D array nums, where each nums[i] is a non-empty array of distinct positive integers, we want to identify which integers appear in every array in nums. The result should be sorted in ascending order.

In simpler terms, if you imagine each row as a set of numbers, we want the common numbers across all sets. The input nums is guaranteed to contain arrays of unique integers, and the total number of integers across all arrays is at most 1000. Each integer is between 1 and 1000. This means we are dealing with small to moderate input sizes and do not have to worry about extremely large numbers or huge arrays.

Edge cases include when there are no common elements at all, when all arrays are identical, or when there is only a single array (in which case the intersection is simply the array itself).

Approaches

The brute-force approach would be to check each element of the first array against all other arrays. We would iterate through every element in the first array and verify its presence in each subsequent array. This approach works because an element must appear in all arrays to be part of the intersection. However, it is inefficient: if there are m arrays with n elements each, this results in O(m * n^2) time complexity, which can be too slow for the upper bounds.

A better approach uses a hash map (or counting array, given the limited range of integers). We can count the frequency of each number across all arrays. After counting, any number whose count equals the total number of arrays is present in every array. This leverages the constraint that numbers are between 1 and 1000 and is much faster than checking every element repeatedly.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m * n^2)	O(1)	Check every element in the first array against all other arrays
Optimal	O(m * n)	O(1001)	Count occurrences using a fixed-size array or hash map, then collect numbers present in all arrays

Algorithm Walkthrough

1. Initialize a counting array count of size 1001 (since numbers range from 1 to 1000) with all zeros.
2. For each array in nums, iterate through its elements and increment the corresponding index in count by 1.
3. After processing all arrays, iterate through count from index 1 to 1000. If count[i] equals the number of arrays (len(nums)), then i is present in every array.
4. Collect all such numbers into a result list.
5. Return the result list, which will already be sorted because we iterate indices in ascending order.

Why it works: The counting array acts as a frequency tracker across all arrays. By comparing the frequency to the total number of arrays, we can guarantee that only elements appearing in all arrays are included. Iterating in numerical order ensures the result is sorted.

Python Solution

from typing import List

class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        count = [0] * 1001
        for arr in nums:
            for num in arr:
                count[num] += 1
        result = [i for i in range(1, 1001) if count[i] == len(nums)]
        return result

In this implementation, we first create a count array to keep track of the frequency of each number. For each number in each array, we increment its count. After processing all arrays, we construct the result list by collecting numbers whose count equals the number of arrays, ensuring these numbers are present in all arrays. The iteration from 1 to 1000 guarantees ascending order.

Go Solution

func intersection(nums [][]int) []int {
	count := make([]int, 1001)
	for _, arr := range nums {
		for _, num := range arr {
			count[num]++
		}
	}
	result := []int{}
	for i := 1; i <= 1000; i++ {
		if count[i] == len(nums) {
			result = append(result, i)
		}
	}
	return result
}

The Go solution mirrors the Python solution. We use a fixed-size slice of 1001 integers for counting. The final iteration from 1 to 1000 ensures ascending order, and we append numbers that appear in all arrays. Go handles slices efficiently, so appending is safe and maintains order.

Worked Examples

Example 1: nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]

Step	count array snapshot (only non-zero entries)	Explanation
After first array	count[1]=1, count[2]=1, count[3]=1, count[4]=1, count[5]=1	Count numbers from first array
After second array	count[1]=2, count[2]=2, count[3]=2, count[4]=2, count[5]=1	Count numbers from second array
After third array	count[1]=2, count[2]=2, count[3]=3, count[4]=3, count[5]=2, count[6]=1	Count numbers from third array
Collect result	[3,4]	Only numbers with count = 3 (number of arrays) are included

Example 2: nums = [[1,2,3],[4,5,6]]

Step	count array snapshot	Explanation
After first array	count[1]=1, count[2]=1, count[3]=1	Count first array
After second array	count[4]=1, count[5]=1, count[6]=1	Count second array
Collect result	[]	No number has count = 2, so intersection is empty

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * n)	Iterate through each element of each array once; m = number of arrays, n = average length of arrays
Space	O(1001)	Fixed-size counting array regardless of input size

The reasoning for time complexity is that we only iterate through all elements of all arrays once. Space complexity is constant because the counting array size is fixed at 1001, independent of the number of input arrays or their sizes.

Test Cases

# test cases
solution = Solution()

assert solution.intersection([[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]) == [3,4]  # Example 1
assert solution.intersection([[1,2,3],[4,5,6]]) == []  # Example 2
assert solution.intersection([[1]]) == [1]  # Single array
assert solution.intersection([[1,2],[1,2],[1,2]]) == [1,2]  # All arrays identical
assert solution.intersection([[1,2,3],[2,3,4],[3,4,5]]) == [3]  # Single common element
assert solution.intersection([[1,1000],[1000,1]]) == [1,1000]  # Min/max elements
assert solution.intersection([[1,2,3],[1,2],[1]]) == [1]  # Nested subsets

Test	Why
[[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]	Multiple arrays with intersection
[[1,2,3],[4,5,6]]	No common elements
[[1]]	Single array
[[1,2],[1,2],[1,2]]	All arrays identical
[[1,2,3],[2,3,4],[3,4,5]]	Single common element
[[1,1000],[1000,1]]	Edge numbers (min and max)
[[1,2,3],[1,2],[1]]	Nested subsets

Edge Cases

One important edge case is when there is only one array in nums. In this scenario, the intersection is trivially the array itself because there is nothing else to compare against. Our implementation naturally handles this because the counting array will match the number of arrays (1) for all elements in that single array.

Another edge case is when no elements are common across arrays, as in [[1,2,3],[4,5,6]]. A naive implementation might incorrectly return elements from the first array, but our counting array ensures that only elements appearing in every array are included. Since no element meets the requirement, an empty list is returned.

Finally, arrays containing maximum and minimum allowed integers (1 and 1000) can be tricky for implementations using indexing. We correctly handle this by using a counting array of size 1001 and indexing directly by the number value, so both 1 and 1000 are correctly counted and included if present in all arrays.