jeremy.md

Problem 350: Intersection of Two Arrays II

Initial thoughts (stream-of-consciousness)

• We'll likely need to start by sorting the arrays. Time needed: $O(n \log n)$, where array lengths are $O(n)$.
• Maintain two counters, $i$ and $j$, to keep track of where we are in each list
• We'll want to loop until at least one list has been exhausted (after that point we can't have any more overlap anyway, so we don't need to do any more computation)
• There are no super long lists, so sorting will (hopefully) be OK
• List elements are all integers, so no specialized equality tests are needed

Refining the problem

• Probably start with a while loop. i will track our position in nums1 and j will track our position in nums2.
• We can maintain a list of matches, x
• If nums1[i] == nums2[j] append nums1[i] to x and increment i and j
• Otherwise...let's see. If nums1[i] is larger than nums2[j] then we should increment j, and vice versa.
• If i is bigger than len(nums1) OR if j > len(nums2), return x
• Outside of the loop, return x

Attempted solution(s)

classSolution: defintersect(self, nums1: List[int], nums2: List[int]) ->List[int]: nums1.sort() nums2.sort() x= [] i=0j=0while (i<len(nums1)) and (j<len(nums2)): ifnums1[i] ==nums2[j]: x.append(nums1[i]) i+=1j+=1elifnums1[i] >nums2[j]: j+=1else: # nums1[i] < nums2[j]i+=1returnx

• Given test cases pass
• New test case: nums1 = [5] and nums2 = [5, 4, 3, 2, 1, 5] (passed)
• Another test case: nums1 = [1] and nums2 = [2, 3, 4] (passed; also tried swapping nums1 and nums2

Submitting....

Solved!