Java O(min(n1, n2)) space O(n1+n2) time one HashSet


  • 1

    In case one array is significant bigger than the other, the solution guarantees the optimal space and time

    public class Solution {
        public int[] intersection(int[] nums1, int[] nums2) {
            if (nums1.length > nums2.length) {
                return intersection(nums2, nums1);
            }
            
            Set<Integer> set = new HashSet<>();
            for (int num : nums1) {
                set.add(num);
            }
            
            List<Integer> list = new ArrayList<>();
            for (int num : nums2) {
                if (set.remove(num)) {
                    list.add(num);
                }
            }
            int[] intersection = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
                intersection[i] = list.get(i);
            }
            return intersection;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.