algoadvance

Given a 2D integer array nums where nums[i] is a list of integers, return a list containing all the integers that are present in each and every array of nums sorted in ascending order.

Clarifying Questions

1. What is the expected input format and constraints?
   • Input: nums is a list of lists, where each inner list contains integers.
   • Constraints:
     • 1 <= nums.length <= 1000
     • 1 <= nums[i].length, nums[i][j] <= 1000
2. What should be the output if there is no common integer in all arrays?
   • Output: An empty list if no common integer is found in all arrays.
3. Can the integers within each sub-array be negative or are they only positive?
   • The constraints imply only positive integers since it is given nums[i][j] <= 1000.
4. Can the arrays be empty?
   • Based on the constraints (1 <= nums.length and 1 <= nums[i].length), no subarray or the main array will be empty.

Strategy

1. Create a Function: Create a function called intersection_of_arrays which will take a list of lists as input.
2. Using Sets: Utilize Python’s set to keep track of the intersection:
   • Start with the first sub-array converted to a set.
   • Iterate through the remaining sub-arrays, updating the set by taking an intersection with each new sub-array.
3. Sorting: Convert the final set to a sorted list before returning it.

Code

from typing import List

def intersection_of_arrays(nums: List[List[int]]) -> List[int]:
    if not nums:
        return []

    # Start with the set of the first list
    intersection_set = set(nums[0])

    # Find the intersection with all remaining lists
    for arr in nums[1:]:
        intersection_set &= set(arr)

    # Return the sorted list of the result
    return sorted(intersection_set)

# Example usage:
nums = [
    [1, 2, 3],
    [4, 5, 2], 
    [2, 8, 9]
]
print(intersection_of_arrays(nums))  # Output: [2]

Time Complexity

• Conversion to set for each sub-list: O(N) per sub-array of size N (since the length can be at most 1000).
• Intersection operation: O(N) for each intersection (again using max sub-array length N).
• Sorting the final result: O(M log M) where M is the size of the intersection set.
  • In the worst case, M is the smallest size of any sub-array.

Thus, the total complexity is:

• Best case: O(M log M), when all the numbers intersect quickly.
• General case: O(K * N + M log M), where K is the number of arrays and N is the maximum length of any sub-array.

The approach efficiently handles the problem within constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?