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:

1Input: nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]
2Output: [3,4]
3Explanation: 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:

1Input: nums = [[1,2,3],[4,5,6]]
2Output: []
3Explanation: 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.

Solution

This problem has constraint that each of the numbers are less than 1001. This means we can store them in an array of size 1001 where each element at a specific index will be the one from input array. Now, we iterate through the input array nums and update the frequency in our newly created array count. Once we have iterated through all elements of the nums array, the frequency for the common elements in the count array will be equal to nums.length. This gives us advantage in that we don’t have to sort the result before inserting into output linked list. However, the problem with this approach is that even if we have let’s say only 3 elements in each array of nums, we will end up creating this count array of size 1001. If there was constraint that each element can be up to 100000, then this solution would become prohibitively expensive in terms of space complexity.

 1class Solution {
 2    public List<Integer> intersection(int[][] nums) {
 3        if (nums == null || nums.length == 0) {
 4            return null;
 5        }
 6        int[] count = new int[1001];
 7        List<Integer> result = new ArrayList<>();
 8        int length = nums.length;
 9        // Add count of each of the element. This can grow up to 1000 because max size is 1000
10        for (int i = 0; i < length; i++) {
11            for (int j = 0; j < nums[i].length; j++) {
12                count[nums[i][j]]++;
13            }
14        }
15        for (int i = 0; i < 1001; i++) {
16            if (count[i] == length) {
17                result.add(i);
18            }
19        }
20        return result;
21    }
22}

Another option is to use HashMap to store the frequency. This gives us advantage that we will end up having only as many keys as the number of unique elements in nums array. This saves us in terms of space complexity. However, at the end once we have inserted all frequencies, we will still have to sort the keys of this HashMap because the problem has asked us to return the output in the ascending order which adds a bit of time complexity.

 1class Solution {
 2    public List<Integer> intersection(int[][] nums) {
 3        if (nums == null || nums.length == 0)
 4            return null;
 5        Map<Integer, Integer> map = new HashMap<>();
 6        List<Integer> result = new ArrayList<>();
 7        int length = nums.length;
 8        // Add count of each of the element. This can grow up to 1000 because max size is 1000
 9        for (int i = 0; i < length; i++) {
10            for (int j = 0; j < nums[i].length; j++) {
11                map.put(nums[i][j], map.getOrDefault(nums[i][j], 0) + 1);
12            }
13        }
14        for (int i = 0; i < 1001; i++) {
15            if (map.getOrDefault(i, 0) == length) {
16                result.add(i);
17            }
18        }
19        return result;
20    }
21}
  • Time Complexity: O(m x n)
  • Space Complexity: O(1) because at most we can have upto 1000 keys stored in HashMap.