Problem Description

You are given a 2D integer array nums where each nums[i] is a non-empty array containing distinct positive integers. Your task is to find all integers that appear in every single array within nums, and return them sorted in ascending order.

For example, if nums = [[3,1,2,4,5], [1,2,3,4], [3,4,5,6]], the integers that appear in all three arrays are 3 and 4, so you would return [3,4].

The solution uses a counting approach with an array cnt of size 1001 (to handle positive integers up to 1000). It iterates through each sub-array in nums and increments the count for each number found. After processing all sub-arrays, any number whose count equals len(nums) must have appeared in every sub-array. These numbers are collected and returned in ascending order.

The key insight is that if a number appears in all n sub-arrays (where n = len(nums)), its count will be exactly n since each number appears at most once per sub-array (given that each sub-array contains distinct integers).

Intuition

When we need to find elements that appear in all arrays, we're essentially looking for the intersection of multiple sets. The natural question is: how can we efficiently track which elements appear in all arrays?

Since each sub-array contains distinct integers, we know that any given number can appear at most once in each sub-array. This means if we have n sub-arrays total, and a number appears in all of them, it will appear exactly n times across the entire 2D array.

This observation leads us to a counting strategy: instead of computing complex set intersections, we can simply count how many times each number appears across all sub-arrays. If a number's count equals the total number of sub-arrays, it must be present in every single one.

Why use an array of size 1001? The problem states we're dealing with positive integers, and in most programming contexts, this typically means integers from 1 to 1000. Using a fixed-size array allows us to count occurrences in O(1) time per number, making our solution very efficient.

The beauty of this approach is its simplicity - we transform a set intersection problem into a counting problem. By iterating through all elements once and maintaining counts, we avoid the complexity of comparing multiple arrays against each other. The final step of checking cnt[x] == len(nums) elegantly identifies our answer, and since we iterate through the count array in order, the results are naturally sorted.

Learn more about Sorting patterns.

Solution Approach

The solution uses a counting approach to find integers present in all sub-arrays. Let's walk through the implementation step by step:

Step 1: Initialize the Counter Array

cnt = [0] * 1001

We create a counter array of size 1001 to track occurrences of each positive integer (indices 1 to 1000). Each index represents a number, and the value at that index represents how many sub-arrays contain that number.

Step 2: Count Occurrences Across All Sub-arrays

for arr in nums:
    for x in arr:
        cnt[x] += 1

We iterate through each sub-array arr in nums. For each number x in the current sub-array, we increment cnt[x] by 1. Since each sub-array contains distinct integers, each number contributes at most 1 to its count per sub-array.

For example, if nums = [[1,2,3], [2,3,4], [3,4,5]]:

• After processing first array: cnt[1]=1, cnt[2]=1, cnt[3]=1
• After processing second array: cnt[2]=2, cnt[3]=2, cnt[4]=1
• After processing third array: cnt[3]=3, cnt[4]=2, cnt[5]=1

Step 3: Identify Common Elements

return [x for x, v in enumerate(cnt) if v == len(nums)]

We use list comprehension to build our result. We enumerate through the counter array, where x is the index (representing the number) and v is the count. We include x in our result only if v == len(nums), meaning the number appeared in all sub-arrays.

Since we iterate through indices in ascending order (0 to 1000), the resulting list is automatically sorted.

Time Complexity: O(n * m) where n is the number of sub-arrays and m is the average length of each sub-array.

Space Complexity: O(1) for the fixed-size counter array (not counting the output list).

Example Walkthrough

Let's trace through the algorithm with a concrete example to see how it finds common elements.

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

Step 1: Initialize Counter We start with cnt = [0] * 1001, creating an array where all counts are initially zero.

Step 2: Process First Sub-array [3,1,2,4,5]

• Visit 3: cnt[3] = 0 + 1 = 1
• Visit 1: cnt[1] = 0 + 1 = 1
• Visit 2: cnt[2] = 0 + 1 = 1
• Visit 4: cnt[4] = 0 + 1 = 1
• Visit 5: cnt[5] = 0 + 1 = 1

After first array: cnt[1]=1, cnt[2]=1, cnt[3]=1, cnt[4]=1, cnt[5]=1

Step 3: Process Second Sub-array [1,2,3,4]

• Visit 1: cnt[1] = 1 + 1 = 2
• Visit 2: cnt[2] = 1 + 1 = 2
• Visit 3: cnt[3] = 1 + 1 = 2
• Visit 4: cnt[4] = 1 + 1 = 2

After second array: cnt[1]=2, cnt[2]=2, cnt[3]=2, cnt[4]=2, cnt[5]=1

Step 4: Process Third Sub-array [3,4,5,6]

• Visit 3: cnt[3] = 2 + 1 = 3
• Visit 4: cnt[4] = 2 + 1 = 3
• Visit 5: cnt[5] = 1 + 1 = 2
• Visit 6: cnt[6] = 0 + 1 = 1

Final counts: cnt[1]=2, cnt[2]=2, cnt[3]=3, cnt[4]=3, cnt[5]=2, cnt[6]=1

Step 5: Find Common Elements We have len(nums) = 3, so we look for numbers with count equal to 3:

• cnt[1] = 2 ❌ (not in all arrays)
• cnt[2] = 2 ❌ (not in all arrays)
• cnt[3] = 3 ✓ (appears in all 3 arrays)
• cnt[4] = 3 ✓ (appears in all 3 arrays)
• cnt[5] = 2 ❌ (not in all arrays)
• cnt[6] = 1 ❌ (not in all arrays)

Result: [3, 4] - These are the only numbers that appear in all three sub-arrays, and they're already in ascending order since we iterate through indices sequentially.

Solution Implementation

Time and Space Complexity

The time complexity is O(N), where N is the total number of elements across all arrays in nums. This is because the code uses two nested loops - the outer loop iterates through each array in nums, and the inner loop iterates through each element in the current array. Each element is processed exactly once with a constant time operation (cnt[x] += 1). The final list comprehension iterates through the fixed-size array cnt of length 1001, which takes O(1001) = O(1) time.

The space complexity is O(1001) = O(1). The code uses a fixed-size array cnt of length 1001 to count occurrences, regardless of the input size. The output list size is bounded by 1001 in the worst case, which is still constant space. Therefore, the space complexity is constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Handling Duplicate Values Within a Single Sub-array

The Pitfall: A common mistake is assuming the algorithm would work correctly even if individual sub-arrays contained duplicate values. If duplicates were present within a single sub-array, the counting approach would over-count that number, leading to incorrect results.

Example of the issue:

# If nums = [[1,2,2,3], [2,3,4], [2,3,5]]
# The number 2 would have count = 4 (2 from first array + 1 + 1)
# This breaks our logic that count == len(nums) means presence in all arrays

Solution: The problem statement guarantees that each sub-array contains distinct integers, so this isn't an issue here. However, if you needed to handle duplicates, you would need to track which arrays contain each number using a set-based approach:

def intersection_with_duplicates(nums):
    frequency_counter = [set() for _ in range(1001)]
  
    for i, array in enumerate(nums):
        for number in array:
            frequency_counter[number].add(i)  # Track which arrays contain this number
  
    result = []
    for value, array_indices in enumerate(frequency_counter):
        if len(array_indices) == len(nums):
            result.append(value)
  
    return result

2. Index Out of Bounds for Large Numbers

The Pitfall: If the input contains numbers greater than 1000, accessing frequency_counter[number] would cause an IndexError.

Example of the issue:

# If nums = [[1,2,1001], [1001,2,3]]
# frequency_counter[1001] would raise IndexError: list index out of range

Solution: Add bounds checking or use a dictionary instead of a fixed-size array:

def intersection_safe(nums):
    frequency_counter = {}
  
    for array in nums:
        for number in array:
            frequency_counter[number] = frequency_counter.get(number, 0) + 1
  
    result = []
    for number, count in frequency_counter.items():
        if count == len(nums):
            result.append(number)
  
    return sorted(result)  # Need to sort since dictionary iteration order isn't guaranteed

3. Forgetting to Return Sorted Results

The Pitfall: When using a dictionary-based approach or any method that doesn't naturally maintain order, forgetting to sort the final result would violate the problem requirement of returning numbers in ascending order.

Solution: The array-based approach naturally produces sorted results since we iterate through indices in order. For dictionary-based approaches, always remember to sort the final result before returning.