Lintcode 793. Intersection of Arrays

Give a number of arrays, find their intersection, and output their intersection size.

Example

Example 1:

 Input:  [[1,2,3],[3,4,5],[3,9,10]]
 Output:  1
 
 Explanation:
 Only '3' in all three array.

Example 2:

 Input: [[1,2,3,4],[1,2,5,6,7][9,10,1,5,2,3]]
 Output:  2
 
 Explanation:
 The set is [1,2].

Notice

• The total number of all array elements is not more than 500000.
• There are no duplicated elements in each array.

Code (Java):

public class Solution {
    /**
     * @param arrs: the arrays
     * @return: the number of the intersection of the arrays
     */
    public int intersectionOfArrays(int[][] arrs) {
        // write your code here
        if (arrs == null || arrs.length == 0) {
            return 0;
        }
        
        return intersectionOfArraysHelper(0, arrs.length - 1, arrs).length;
    }
    
    private int[] intersectionOfArraysHelper(int start, int end, int[][] arrs) {
        if (start == end) {
            return arrs[start];
        }
        
        int mid = start + (end - start) / 2;
        int[] left = intersectionOfArraysHelper(start, mid, arrs);
        int[] right = intersectionOfArraysHelper(mid + 1, end, arrs);
        
        return intersectionOfTwoArray(left, right);
    }
    
    private int[] intersectionOfTwoArray(int[] left, int[] right) {
        Arrays.sort(left);
        Arrays.sort(right);
        
        int i = 0;
        int j = 0;
        
        List<Integer> ans = new ArrayList<>();
        while (i < left.length && j < right.length) {
            if (left[i] == right[j]) {
                ans.add(left[i]);
                i++;
                j++;
            } else if (left[i] < right[j]) {
                i++;
            } else {
                j++;
            }
        }
        
        int[] ans2 = new int[ans.size()];
        for (i = 0; i < ans2.length; i++) {
            ans2[i] = ans.get(i);
        }
        
        return ans2;
    }
}