Another from the archives! This one is interesting because, at least to me, I found it was more an algorithmic/math question, rather than a straight application or exploration of a data structure.

By that same token I’m not sure I’d use this as an interview question, nor as a homework question. It’s building the confidence that we have the “right” pairing is the tricky part, I think. When I’ve seen students confront an algorithm that ultimately has a greedy solution, they often intuit the greedy algorithm as an approach, but won’t have the rigor to be able to be confident it’s the right one (or they don’t even know it might not be the right one, and an, e.g., dynamic programming solution is called-for). I don’t know how I feel about students “accidentally” getting the right answer: when Leetcode finally lights up all green for them, I’d imagine they view that as a certificate that they fully understand the answer. Maybe not!

Anyways, I fortunately recorded my original thoughts in a comment, which I’ve extracted here:

Approach and Solution

The algorithmic question here is somewhat interesting! We don’t just want to pair the largest half with the smallest half. Is the intuition that we want to pair the “closest” values? The max value cannot be chosen, as it’d be paired with something smaller. But the second-max value can be chosen if we pair it with the max. Do we always want to do that?

That’s suggesting a greedy algorithm. Find the “largest-still-pickable” value. Let’s say there’s some other, better pairing. Then we have at least two pairs (a, b) (c, d) where a < b, c < d, but also b > c. In that case we have: a, c, b, d (or a, c, d, b, or c, a, b, d, or c, a, d, b) in terms of sorting by order.

Presumably what I want to say is that swapping b, c here would increase the result. Let’s see: previously we’d have a + c, but by swapping we get either b or d (both of which are bigger than c), and either a or c.

WLOG can we say that a < c? Probably! I think that’s enough to go on here.

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        if (nums.size() == 0) { return 0; }
        std::sort(begin(nums), end(nums));
        assert(nums.size() % 2 == 0);
        int result = 0;
        for (int i = 0; i < nums.size(); i += 2) {
            result += nums[i];
        }
        return result;
    }
};

I think this is the first “greedy algorithm” solution I’ve posted here. So it trailblazes a new category, here.