Java O(n) Easy To Understand, Optimal Solution


  • 0
    B

    Explanation
    The idea to this question is to transform nums1, nums2 into their set equivalents - this eliminates duplicates and allows for O(1) lookup. Then, we iterate through one of the sets, checking if any given element resides in the another set. If true, we append to result.

    Time Complexity
    The time complexity is O(n) where n = max(nums1.length, nums2.length), since we scan through both nums1, nums2 to populate our sets set1, set2.

    class Solution {
        public int[] intersection(int[] nums1, int[] nums2) {
            // Populate both sets
            Set<Integer> set1 = new HashSet<>();
            Set<Integer> set2 = new HashSet<>();
            for (int num : nums1) {
                set1.add(num);
            }
            for (int num : nums2) {
                set2.add(num);
            }
            
            // Iterate through set1, check for same elems in set2
            List<Integer> list = new ArrayList<>();
            Iterator<Integer> itr = set1.iterator();
            while (itr.hasNext()) {
                Integer num = itr.next();
                if (set2.contains(num)) {
                    list.add(num);
                }
            }
            
            // Transform our list into an array
            int [] result = new int [list.size()];
            for (int i = 0; i < list.size(); i++) {
                result[i] = list.get(i);
            }
            return result;
        }
    }
    

Log in to reply
 

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