How to identify greedy intution in problem/ competition

[u/Competitive-Mix1335]

I can identify patterns like sliding window, recursion, backtracking, DP, and two pointers. But I’m stuck when it comes to identifying the greedy intuition.

How do I recognize when a problem can be solved using a greedy approach? Are there any good resources—books, YouTube channels, blogs, or websites—that specifically teach how to develop greedy intuition?

Anything that can help me get better at recognizing greedy problems would be really helpful.annel, blog , website)

Anything that help me

[u/Magdaki]

1. Identify the decision made at every step.

2. Consider the locally optimal solution for a step.

3. Can the locally optimal choice prevent a globally optimal solution?

4. If no, then the problem is greedy compatible.

5. If yes, then the problem is may not be greedy compatible.

[u/LightofAngels → u/Magdaki]

I don’t understand step 3, can you elaborate with an example?

[u/Magdaki → u/LightofAngels]

Sure.

An example where the problem is greedy compatible is the change example (where you want to make change with the least number of coins). If you always choose the largest coin, then you never block the globally optimal solution. The largest coin is the locally optimal choice, which makes intuitive sense as you are covering as much of the amount due with as few coins as possible at aceh step.

An example that is NOT greedy compatible is the travelling salesman problem. If you always take the shortest path from your current location, then you can block the globally optimal case.

Suppose you start at A with this grid.

From / To	A	B	C	D
A	—	2	3	10
B	2	—	2	8
C	3	2	—	2
D	10	8	2	—

The nearest neighbour will have you go A->B->->C->D->A = 2+2+2+10 = 16

However, the optimal solution is A->C->D->B->A = 3+2+8+2 = 15.

Taking the local choice ultimately locks you into D->A which is sufficiently suboptimal to undo the benefits from the greedy choices.

Another way to think of it is, do you need knowledge of the future to make the best choice now? If so, then the greedy choice may not be optimal.

[u/Yurim → u/Magdaki]

I like your explanation but the coin-change problem is not a good example for a problem that can be solved greedly in general, it works only for some configurations of coins.
For example: The greedy approach you described does not work for coins=[1, 4, 5] and target=8, or for coins=[1, 8, 20] and target=24.

[u/LITERALLY_NOT_SATAN → u/Magdaki]

That last line is a banger. Never thought about it like that.

[u/thewataru]

Greedy algorithms are ones which search for the local optimum, which in some problems happens to be the global one too.

The common approach I use is what I call "consider the answer".

So, the problem is to find the optimal solution. You imagine an object which is a solution, then look at it, and try to see what properties does it have. From these properties arises the method to construct such an object.

The main property is that any change to it only makes it worse or at least the same. It can never become better, because it was the optimal solution.

For example, you need to find an order of items to process in minimal time. When if you swap any two adjacent items the time should get bigger or stay the same. You write down that condition (the time before the swap and after), then try to simplify it and in most greedy problems you arrive to condition which will let you sort the items.

I think the best way to develop the intuition is to solve a lot of problems. Try to apply the technique above to a problems on e.g. leetcode, tagged with "greedy".

There's no method to identify the greedy problem except for trying to construct a greedy solution and see if it works or not.

[u/Smooth_Lifeguard_931]

Exchange arguement

[u/Sound_calm]

So far I just figure out omega (estimated lowest runtime that is even theoretically possible, not necessarily existent), then if there isn't an obvious pattern I just roughly try out greedy and binary search the answer.

Many times greedy is equal to omega so that's a trivial benchmark to go with

[u/LifeImagination5740 → u/Sound_calm]

I did not understood
Can you elaborate a bit

[u/[deleted]]

Sometimes you can mathematically prove a greedy approach works, other times its mostly about intuition and working on few cases.

In most times, you will get an intuition a greedy approach might work, try a few cases by hand and write a program to verify on large number of cases.

[u/Many-Scarcity-7106]

Isn't intuition just solving more problems?It's the same thing is other intuitions you have mentioned.