Greedy vs DP: When Sorting Fails the Interview

The Sorting Trap That Costs You the Offer

You sort the array, apply a greedy loop, get the right answer on test cases 1-3, then watch test case 4 fail. The interviewer asks, "What's your approach?" You explain the greedy logic. They nod. "Can you think of a case where sorting doesn't help?"

This happens because sorting creates a local optimum illusion. You see the elements in order and assume the greedy choice at each step leads to the global optimum. But some problems have overlapping subproblems where earlier greedy decisions invalidate later ones.

Here's the classic trap: Partition to K Equal Sum Subsets (LeetCode 698). Given an array and integer k, can you partition it into k subsets with equal sum?

Why Sorting + Greedy Fails

First instinct: sort descending, greedily assign each element to the subset with the smallest current sum.

def canPartition_greedy(nums, k):
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k

    nums.sort(reverse=True)  # Largest first
    buckets = [0] * k

    for num in nums:
        # Greedy: put in the emptiest bucket
        min_idx = min(range(k), key=lambda i: buckets[i])
        if buckets[min_idx] + num > target:
            return False  # Early termination if exceeds target
        buckets[min_idx] += num

    return all(b == target for b in buckets)

# Test case that breaks it
print(canPartition_greedy([4, 3, 2, 3, 5, 2, 1], 4))  # False (wrong)

---

Continue reading the full article on TildAlice