Motivation
Someone asked on Discord how to identify greedy solutions in problems where they aren’t very obvious. They mentioned two problems in particular: Jump Game and Container With Most Water, and said that greedy felt unintuitive to them for these.
To be honest, when I first attempted these problems, I couldn’t solve them completely on my own. Even when I practiced greedy problems intentionally — knowing beforehand that they were greedy — I still had the same doubts. Greedy didn’t feel natural to me either. So when I saw someone ask this question on Discord, I decided to think about it a bit more deeply and see what I would discover.
I focused mainly on these two problems. For each, I first followed my instinct and arrived at whatever solution it led me to. Then I tried to trace that intuition back, contrast it with the greedy solution, and understand why one approach felt more natural than the other.
Container With Most Water
You’re given an array of heights where each index represents a vertical line. The goal is to choose two lines such that the container they form holds the maximum amount of water.
In this problem, my instinct surprisingly led me directly to the intended greedy solution. One reason might be that I couldn’t see any meaningful way to optimize the brute-force approach I initially thought of. Instead of sticking to brute force and trying to improve it, I started approaching the problem differently.
I first clearly defined the goal: maximizing the area. Ideally, this means having both maximum width and maximum height, but realistically that won’t always be possible. That reframed the problem for me as finding the best compromise between the two. I started with the largest possible width and then tried to improve the height if possible, even if it meant sacrificing some width, hoping that the increase in height would compensate for it.
While writing this, I realized that the greedy approach can also be seen as an optimization of brute force. In brute force, we consider every possible container and compare their areas. In the greedy solution, we don’t build every container. Instead, we deliberately discard containers that we know can never be optimal, because the current greedy choice already dominates them. This is what makes the approach both efficient and safe.
Jump Game
You’re given an array where each value tells you the maximum number of steps you can jump forward from that index. Starting at index 0, the question is simply whether you can reach the last index or not.
For Jump Game, greedy was not an obvious choice for me at first. I think this was because I was framing the problem strictly as “how do I reach the target?” — which naturally leads to a DP-style solution. However, when I later saw the greedy solution (which is more efficient), I realized that a different framing makes it feel much less unintuitive.
If the problem is viewed as a distance problem — where index 0 is the farthest point from the end, the goal becomes reaching as far as possible from the start and checking whether that reach eventually covers the last index. From this perspective, the greedy solution is simply about expanding reachability step by step, rather than aiming for the target directly.
Conclusion
I think part of the reason greedy feels scary to me is that I struggle to prove its correctness, even to myself. It often feels like I'm taking a blind shot and hoping it works, rather than doing the "real work" of reasoning properly. That's probably because I don't yet understand greedy algorithms beyond their informal definition.
My takeaway is that getting better at reasoning about why a greedy choice is safe would make these solutions feel more natural. Along with that, reframing problems in different ways and reflecting on how an intuition-led solution actually works seems like a good way to build greedy intuition over time.
Top comments (0)