The creation of a set from an array of n elements takes O(n) time complexity. Let us think that the first array is of length n and the second array is of length m.
Then the final time complexity of the above implementation would be O(m+n). Let us explain this step-by-step:
- We create a set from the first array:
O(n). - We traverse through the second array with
filtermethod which takesO(m). In this traversal process, we check if that element exists in the set from the first array which takesO(1). - Finally we create the resulting array from the filtered second array which takes
O(m)worst time. Remember, although we may return an array, it is crucial to building a set first. The reason is to remove duplicates from the filter of the second array.
So, the final time complexity is O(n + m + m) = O(m+n).
xxxxxxxxxx65
'PASSED: `intersection([4,17,4,4,15,16,17,6,7],[15,2,6,20,17,17,8,4,5])` should return `[15,6,17,4]`'var assert = require('assert');function intersection(nums1, nums2) { // fill this in return [];}try { assert.deepEqual(intersection([6, 0, 12, 10, 16], [3, 15, 18, 20, 15]), []); console.log( 'PASSED: `intersection([6,0,12,10,16],[3,15,18,20,15])` should return `[]`' );} catch (err) { console.log(err);}try { assert.deepEqual(intersection([1, 5, 2, 12, 6], [13, 10, 9, 5, 8]), [5]); console.log( 'PASSED: `intersection([1,5,2,12,6],[13,10,9,5,8])` should return `[5]`' );} catch (err) { console.log(err);}OUTPUT
Results will appear here.