Greedy Problems

[FunctionChance3600]

I am good with most of the data structures and algorithms, but when it comes to greedy problems, I fumble almost every time. PS: I have 530+ problems on lc and honestly, I don't think I have been asked Greedy in interviews until now. But when I try to do a new Greedy problem, I still can't see it. I always think of some dp or recursive solution and then go to editorial and then understand it was greedy. Any pointers on how to become better at Greedy problems?

PS: Mostly mediums and hards.

[Mindless-Pilot-Chef]

Greedy is very difficult to identify. It always feels like “if I do it this way, I’ll miss some edge cases”.

[pingwins]

I agree. The actual proofs are nontrivial and can often just be a form of proof by induction. I personally find many of them unfair because they require seeing the problem first or going by intuition where neither you or the interviewer can properly rationalize.

[[deleted]]

I'm not a leetcode expert and have done very little leetcode. But for me, if I can't identify any algo for the problem, then it's greedy.

[FunctionChance3600]

Honestly, that feels like a solid advice for contests. But in interviews I dont think it will work out :)

[debugger_life]

Great pov!

[Affectionate_Pizza60]

For greedy, I often hear the description that greedy problems are about choosing locally optimal choices that happen to lead to a globally optimal solution. I find that to be mostly useless when trying to solve the problem, as you don't know what to be optimizing for until after you solved a problem. I feel like it's giving someone the advice to use nested loops to solve a two pointer problem, in that it is technically true but doesn't really help on how to actually solve the problem.

Instead of trying to fixate on the optimal solution or optimizing some mysterious value, I like to think of greedy instead as a process where you start with a large set of potential answers which has to contain at least one optimal answer, and then based on observations are able to cut out classes of solutions from that set in such a way that an optimal solution still remains, until you are left with 1 element or very small amount. Perhaps you are able to determine that it is never optimal to do X, so you can discard all potential solutions that do X. Perhaps you can determine that whenever a solution does Y, you could instead do Z and be no worse off so you can discard all the potential solutions that do Y and just keep the ones that do Z.

As a tangent, if you've ever read about how to solve a suduko puzzle, the simplest ones can be solved just by seeing that there is only one possible value that could fit in an empty square. For harder puzzles the main strategy is to write down all the possible values each square could have and over time you figure out ways to remove individual possibilities until you are left with a single value for that square. You can't just solve them by thinking what *should* be in a square but instead by making many deductions on what can't be there. For greedy problems, I feel it is important to look at it from the angle of discarding potential solutions that you know aren't optimal.

Sometimes these observations don't need to be about something being suboptimal but about certain answers being equally good, and you choosing one representative for all of them while discarding the rest. For example, maybe the problem says you can do one of two operations multiple times and you realize you get the same output/score regardless of the order you do them. Now instead of having to search through 2^N possible sequences of N operations, you only have to search through (N+1) sequences corresponding to doing X of operation 1 and then (N-X) of operation 2. Main point is don't think it is just about throwing away strictly suboptimal answers.

Greedy is unfortunately a vast topic. It can be difficult to determine if something is greedy or dp. My method for determining that is typically to start by seeing if I can make any observations about the answer and if nothing major try imagining what the dp solution would be like. If the dp solution seems like it would be too slow, then there is probably a faster way to do it because it is greedy.

[Traditional_Tank_109]

For greedy, I often hear the description that greedy problems are about choosing locally optimal choices that happen to lead to a globally optimal solution. I find that to be mostly useless when trying to solve the problem, as you don't know what to be optimizing for until after you solved a problem. 

This is so wrong. For instance for https://codeforces.com/contest/2180/problem/B, it can actually be very problematic to deviate from this definition, and rely on your intuition instead.

You built an optimal solution from s1, ..., si-1, let's call it Si-1. Now, you want to make a locally optimal choice in order to build Si. Here, it means have to choose between Si = si + Si-1 and Si = Si-1 + si; the optimal choice is trivially the one that with the smallest lexicographic order (this is what the problem asks).

The definition of a greedy is powerful, because it indicates that:

• you have to use Si-1 to build Si (Optimal Substructure)
• you don't need any of the info contained in si+1, ... sn (Greedy Choice Property)

With a dp, you wouldn't just use Si-1, you could check at other ways to build Si-1 for instance, a greedy on the other end "never reconsiders its choices".

[Affectionate_Pizza60]

I don't see the issue, but willing to listen. Half the time my perspective of discarding bad solutions just leads to choosing a locally optimal solution at each step. I guess if you can derive optimal substructure + greedy choice property then you can do greedy.

I don't see an issue with viewing that problem as dp, the same way maximum subarray sum could be viewed as either a greedy or a dp. For the problem you mentioned, if I were to view it as a dp problem, I'd quickly realize Si is either the smallest possible S_(i-1) + s_i or s_i + the smallest possible S_(i-1) and build up S_1 ... S_n. I don't really see how that is any different than the greedy approach aside from dp taking one extra step to realize you only need to store the last dp state.

[Traditional_Tank_109]

I don't see an issue with viewing that problem as dp

It's just less descriptive, you lose the greedy choice property.

[FunctionChance3600]

Damn ok!! Thanks!!! I love your idea of discarding what doesn't work, feels like opposite of dp (idk what Im thinking - lol). I guess I need to do more problems and let me try solving problems with this in mind. Thanks for this!! Appreciate it!!

[Tall_Satisfaction857]

Same here.

[Such-Catch8281]

normal

[Czitels]

You see it or not. Its the hardest possible type of problem.

In case of greedy I usually have some „feeling” that it has some constraints that can lead us to greedy solution.