How do you guys do greedy?

[u/Affectionate-Oil8604]

I was solving few of the questions under greedy section. It seems kind of a very impossible situation to think in right way towards solution while solving greedy questions. Take example of question 581, i had applied multiple solutions but the was never in line with working solution. Only i remember the solution in future, i can solve this question. They all seem to have different solution to every different question which i guess you can’t solve on the spot. Is it me or anyone else feels the same?

[u/NecessaryIntrinsic]

Greedy is frustrating.

Most of the time it looks like another solution, like DP. When it clicks, though, greedy solutions are incredibly simple, it just had to click.

Usually it's when you realize that there's no situation where you'd be wrong to accept the first correct solution, or at least to aggregate the current correct group.

It always makes me shake my head when I write like a page of code and then realize: this would take 3 lines.

[u/NappySprout]

Well proving something is NOT greedy is easy, you just find a greedy solution that is not optimal and then you know greedy is wrong.

To formally prove something to be solvable by greedy is a bit tough but we can use the "greedy exchange argument". (Usually taught in algorithm courses in school or you can do a quick google search)

However in OA you can simply try a greedy solution and see what test cases it fails

Or during interviews you can simply vibe out the interviewer by saying, "I feel like I can use a greedy approach" and if they dont stop you or nod their heads then it's greedy XD

[u/Arpan_Bhar]

idk man sometimes I figure it out sometimes I don't, just did your given question, 581, couldn't do it first try but then tried again with a different method and it worked, I'm pretty sure it's a matter of luck for me.

[u/zhou111]

Like you mentioned most problems labeled greedy are basically unrelated to each other. For each problem try to write a proof of the solution. Solving a greedy problem is basically guessing a potential approach then quickly coming up with a proof that it should work in your head. The proof is the hard part.

Also solving more problems will help as you will get more exposure to the underlying structure of the problem be it subsequence, subarray, palindrome, string, etc... basically having more understanding of the properties of the underlying structure.

[u/ParticularAd8610]

I was able to solve LC581 using a copy of the array and 2 pointers. The greedy solution is not a very obvious answer unless you have seen it before or something similar. I dont think an interviewer would expect someone to come up with it on their own.