Regarding Greedy

I have started learning greedy algorithms, and i don’t find any particular way to solve the questions,
i think greedy is just needs to think for optimal way by using more logic?
then why it is called as greedy algorithm?
Correct me if i am wrong.

A greedy algorithm makes choices without thinking about the future (aka locally optimal choices). Proving that greedy algorithms are correct does require more logic.

6 Likes

is it true that greedy always require recursion/backtracking? can’t we do directly by brute force?
can you plz mention some of the questions with solutions of greedy from beginner to advance.
Thanks for the reply

Greedy is kind of the opposite of recursion/backtracking as it is usually iterative. Greedy is also different from brute force as greedy does not consider all solutions.

3 Likes

I don’t have a list of greedy questions, but you can go on sites and filter problems by greedy tags.

3 Likes

Try hackerrank and hackerearth problems too
they have a whole section :slight_smile:


2 Likes

Greedy doesn’t necessraily give an optimal solution, but works if the choice we make at every individual step counts, rather than the whole picture. If you can prove your greedy solution, you have no need to look further, but if you’re unsure, you can read below.

As a rule of thumb, greedy appears in following scenarios:

  1. You’re sorting the array then going through it in a fixed manner (one sided traversal, two pointers, etc)
  2. Using a sorted data structure (sets,map,priority queue) and going through the elements one by one.

While going through these elements, you may be deciding between a min/max or a similar operation at every step.
Good luck. :slight_smile:

1 Like