Another from the archives. This is actually something I like as an interview question, so I suppose maybe that means I should change my interview question. I suppose candidates need to know what a set is, but given the domains I work in I think that’s a fair requirement. This question is to take two arrays of integers, and return their set-intersection.

I think a very reasonable approach is to immediately sort the input. After that, as we build the result vector, we can think about the invariants that are maintained: the result vector is in sorted order, and so the “unique-ification” we need to do can follow naturally from that.

Nevermind also the invariants that guide the overall merge-sort-esque loop iterations. We can reason about how we make forward progress.

Code Solution

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        sort(begin(nums1), end(nums1));
        sort(begin(nums2), end(nums2));
        vector<int> result;
        
        int i = 0;
        int j = 0;
        
        while (i < nums1.size() && j < nums2.size()) {
            if (nums1[i] == nums2[j]) {
                if (result.size() == 0) result.push_back(nums1[i]);
                else if (*(result.rbegin()) != nums1[i]) result.push_back(nums1[i]);
                i++;
                j++;
            }
            else if (nums1[i] < nums2[j]) i++;
            else j++;
        }
        
        return result;
    }
};

Extensions

I think some reasonable extensions are: what if the vector-of-ints is sort of a set datatype with certain invariants (e.g., that the contents are always sorted). This suggests the results should also be sorted, but we sort of get that “for free” with the natural approach. I like discussing possible trade-offs of performance depending on the input size.

This is, in my opinion, a nice exercise on loops and arrays. More can be found here.