Category Archives: Greedy Algorithm

Greedy Algorithm, Interview Questions, Strings

Decimal to Roman Numerals (Leetcode)

A sequel to our previous effort, this time going the other way. That the greedy algorithm works here is not too surprising, but maybe there’s a way of concocting a variant of roman numerals where the greedy algorithm wouldn’t work? It’s basically the change-making algorithm. That it works is intuitive, perhaps, but it feels a bit unstable. If somehow we had to do something like this for production, I’d want to really spend out the time characterizing exactly why this works—why we can recast the whole subtractive thing as just a pile of coins. It’s sort of interesting, I guess…

def trySingleString(num, result, symbol, amount):
    if num >= amount:
        return num - amount, result + symbol
    return num, result


def tryRepeatedString(num, result, symbol, amount):
    while True:
        num2, result2 = trySingleString(num, result, symbol, amount)
        if num2 == num:
            return num, result
        num, result = num2, result2


class Solution:
    def intToRoman(self, num: int) -> str:
        assert num >= 0
        result = ""
        num, result = tryRepeatedString(num, result, "M", 1000)
        num, result = tryRepeatedString(num, result, "CM", 900)
        num, result = tryRepeatedString(num, result, "D", 500)
        num, result = tryRepeatedString(num, result, "CD", 400)
        num, result = tryRepeatedString(num, result, "C", 100)
        num, result = tryRepeatedString(num, result, "XC", 90)
        num, result = tryRepeatedString(num, result, "L", 50)
        num, result = tryRepeatedString(num, result, "XL", 40)
        num, result = tryRepeatedString(num, result, "X", 10)
        num, result = tryRepeatedString(num, result, "IX", 9)
        num, result = tryRepeatedString(num, result, "V", 5)
        num, result = tryRepeatedString(num, result, "IV", 4)
        num, result = tryRepeatedString(num, result, "I", 1)
        return result
Greedy Algorithm, Interview Questions

Array Partition (Leetcode)

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.