Overview
Greedy is somehow similar to Binary Search, as they are both intuitive algorithms.
For simple questions, you don't even need to think about them, as it's clear how to do them. For difficult questions, unless you have done similar questions before or have a sudden inspiration, it's very difficult to solve them, and you may not even think of using greedy methods.
The essence of Greedy is to choose the local optima in each stage to approach the gloabl optima. Thus, Greedy is more of a methodology than a concrete algorithm.
Difficulties of Greedy
- When to use Greedy?
- In what kind of questions can we use it? And in what kind of questions we can never use it?
- How to use Greedy?
- How to get the Local Optima? How to get the Global Optima?
When to use Greedy?
Unlike the previously summarized question and techniques, there is really no unified routine for greedy algorithms, let alone template code like backtracking.For Example,
- There is a pile of banknotes, and you can take 10 of them. How can you take the maximum amount?
Specify that you take the largest amount each time, and the end result is that you take away the largest amount of money.
Taking the biggest amount each time is the local optimum, and taking the largest amount of money at the end is the global optimum.
Counter Example,
- If there are a bunch of boxes, and you have a backpack of volume n, how to fill the backpack as full as possible? If you still choose the largest box every time, it won't work. At this time, dynamic programming is needed.
Therefore, when you get an algorithm problem and want to know whether you can use a greedy algorithm, you need to think about three points.
- Is the question about finding the extreme value (finding the optimal solution)?
- Whether other solutions to the question can be seen at a glance (prominence of the question type)
- The global optimum and the local optimum are obviously in conflict (violating the core idea of greedy)
Greedy algorithms always seek extreme values, such as maximum, minimum, least steps, most benefits, etc. Usually, when we see extreme value algorithms, the solution will be either dynamic programming (DP) or greedy.
This may sound a bit arbitrary, but on the other hand, if the problem is not about finding the extreme value, then the greedy algorithm will definitely not be used, and it is very reliable.
For example, chessboard algorithms are obviously backtracking, valid brackets are obviously stacks, and binary tree searches are obviously dfs.
If you can see at a glance the best and most effective solution implied by the question type based on your experience in answering questions, then you can decisively give up greed.
If we can find or discover a counterexample from the question or the test case given in the question to prove that the global optimum cannot be obtained from the local optimum, then the principle of greed is violated and it will be meaningless to continue thinking about greed.
For example, in the knapsack problem, no matter how you choose the greedy strategy, you can always find a counterexample. Or in NP-hard problems such as the Traveling Salesman Problem, these problems are very large in scale or have complex constraints, which makes it impossible to decompose them into solvable sub-problems, so greedy algorithms cannot be used to effectively solve them.
How to use Greedy?
First of all, let me make it clear: there is no routine for greed. To put it simply, it is common sense reasoning plus counterexamples.
Principle 1:- Greedy ideas are often tricky, not intuitive.
- There is no routine or framework for greed. You need to watch and practice more to develop a sense before you can think of greedy ideas.
Summary of practice experience
Intuitive Greedy Problem
Features:- These types of questions are generally simple, which can give people the illusion that the greedy algorithm is very simple, because greed is sometimes close to common sense, or the questions themselves are more lifelike and in line with people's daily logic.
| ID | Problem | Diff | Greedy Strategy |
|---|---|---|---|
| 455 | Assign Cookies | Easy |
Global Optima: Feed the most kids Local Optima: Big cookies assign to kids that eat more / small cookies assign to kids that eat less |
| 860 | Lemonade Change | Easy |
Gloabl Optima: Complete changing for all payments. Local Optima: Once encounters $20 bill, first consume $10 to complete this changing. |
Extreme/Peak Problem
Features:- Most of these questions are of medium difficulty, which will make people who are new to algorithms gradually realize the difficulty of greedy algorithms.
- This type of question is more likely to cause misunderstandings for people who have learned a relatively complete algorithm technology stack but have not yet fully mastered it (but this is only for greedy). Because of extreme value and peak value problems, the first reaction may be to use dynamic programming (many of them can indeed be done with DP, but greedy is definitely more efficient).
- For medium-difficulty questions, it is often not difficult to find the recursive relationship of dynamic programming, while the greedy strategy is not intuitive. In the interview, you should be more pragmatic and use whichever you can think of. Although greedy often has an advantage in time complexity, the dynamic programming algorithm can still better prove the level of the interviewee.
| ID | Problem | Diff | Greedy Strategy |
|---|---|---|---|
| 376 | Wiggle Subsequence | Medium |
Global Optima: The entire sequence has the most local peaks. Local Optima: Delete the nodes on the monotonic slope (excluding the nodes at both ends of the monotonic slope), then the slope can have two local peaks. |
| 53 | Maximum Subarray | Medium |
Global Optima: Select the maximum "continuous sum" Local Optima: When the current "continuous sum" is negative, give up immediately and recalculate the "continuous sum" from the next element, because the "continuous sum" of a negative number plus the next element will only get smaller and smaller. |
| 122 | Best Time to Buy and Sell Stock II | Medium |
This problem can be solved by Dynamic Programming, but Greedy is more efficient Trick: Understanding profit splitting is the key point. If you split the overall profit into daily profits, it is easier to think of greed. Global Optima: Get the highest overall profits. Local Optima: Only collect positive daily profits. |
| 1005 | Maximize Sum Of Array After K Negations | Easy |
The greedy idea is more intuitive: using greedy twice. Frist Greedy:deal with the negative values first (greedy increase)
|
Moving Problem Under Certain Constraints
Features:- Most of these problems are of medium difficulty, with a small number of easy and hard problems, but movement problems of these two difficulty levels are usually not greedy representative.
- The movement problem itself usually implies the use of pointers, so the greedy idea is often aimed at constraints, such as movement loss, movement fuel consumption, and the maximum distance of movement.
| ID | Problem | Diff | Greedy Strategy |
|---|---|---|---|
| 55 | Jump Game | Medium |
Trick: Focus on the coverage, indices within the coverage intervals must be achivable, regardless of how it jumps. Then the problem can be converted to: Whether the jump coverage can reach the end point. Global Optima: Eventaully get the overall maximum coverage to see if you can reach the end point.Local Optima: Move the index each time and take the maximum number of jump steps (maximum coverage). |
| 45 | Jump Game II | Medium |
Trick: Increase the maximum coverage with the minimum number of steps until the coverage covers the end point Global Optima: Reach the end point with minimal steps. Local Optima: Find the maximum coverage of the current step, then walk as much as possible to reach the end of the coverage range |
| 134 | Gas Station | Medium |
Misconception: At first glance, it looks like a simulation question, but the most intuitive way of thinking about simulation is not to be greedy. Trick: The net growth is defined by subtracting the replenishment and loss of each gas station. When running from 0 to the gas station with index i, the cumulative net growth is found to be negative, which means that there is no starting point between 0-i that can complete the journey, and continue to try from i+1. Global Optima: Find a starting position where you can run a lap. Local Optima: The cumulative net growth is negative, which is locally non-optimal and definitely not globally optimal. |
Overlapping Intervals Problem
Features:- The difficulty of this type of problem is generally medium. It is also one of the greedy algorithm problems that have a relatively routine.
- The key to this type of question is to convert the problem to solve the overlapping parts of the intervals, which requires careful identification. The key skill to solve the problem of overlapping intervals is to select a direction (left boundary/right boundary) to sort the array so that the intervals overlap as much as possible.
- After sorting, we only need to pay attention to whether the right side of the overlapping interval can exceed the right boundary of the new interval. On this basis, we can make corresponding treatments for overlapping and non-overlapping situations respectively, so as to solve different problems.
| ID | Problem | Diff | Greedy Strategy |
|---|---|---|---|
| 452 | Minimum Number of Arrows to Burst Balloons | Medium |
Trick: Sort the array to make ballons that are possibly overlapping to get close together Global Optima: Using minmal arrows to shoot all the ballons Local Optima: When ballons are overlapping, shooting with one arrow will lead to minimal arrorws. |
| 435 | Non-overlapping Intervals | Medium |
Trick: Sort the array to make the intervals overlap as much as possible. Global Optima: Makes all intervals not overlapping Local Optima: When two intervals overlap, abandon the right one, which is further (traversed from left to right). |
| 763 | Partition Labels | Medium |
Trick: counts the farthest index for each label. Traverse the characters from the beginning and update the farthest occurrence index of the character. If the farthest occurrence index of the character is equal to the current index, it means that the split point is found. 【It is actually the simulation approach, but in the Greedy idea.】 |
| 56 | Merge Intervals | Medium | Trick: Similar to 452 and 435, but with different presence of returning values. |
Greedy Problems Under Multi-dimensional Constraints
Features:- Most of these questions are hard questions or medium-difficult questions, because they need to consider at least two dimensions (usually at most two dimensions).
- There is a common trick for this kind of questions:
You can consider either side first! Just don't consider both at the same time, or you'll get yourself stuck.
| ID | Problem | Diff | Greedy Startegy |
|---|---|---|---|
| 135 | Candy | Hard |
Dimension 1: Traverse from left to right
|
| 406 | Queue Reconstruction by Height | Medium |
Trick: Sort by height from high to small, and then do Greedy to k Because sorting k first will find that both dimensions are not determined.。 Global Optima: Finally, the insertion operation is completed and the entire queue meets the queue properties of the title.Local Optima: The people with the highest height are inserted first. After the insertion, the people satisfy the queue property. |
Suprising Greedy Problem
Features:- This type of question usually appears in medium and difficult questions. This type of question does not strongly suggest greed, and the questioner may even deliberately mislead. However, when seeking extreme values, it will be found that the idea of seeking extreme values is consistent with the greedy idea.
- Usually, when dealing with this type of problem, it is quite difficult to design and implement a greedy algorithm. Often, it is because one is unable to come up with a greedy framework that is convincing enough to one's self at the first time that one misses out on a greedy solution.
| ID | Problem | Diff | Greedy Strategy |
|---|---|---|---|
| 738 | Monotone Increasing Digits | Medium |
Misconception: By just looking at the question, it looks like a brute force solution, but it timed out, so I had to start with greed. Trick: When traversing numbers from back to front, if you encounter a non-monotonically increasing situation, the previous number is relinquished and the next number can be directly 9. 【Tricky Part: All digits after the last digit must be 9, otherwise the case of 1000000 cannot be processed】 Global Optima: The final number is the largest monotonically increasing number that is smaller than the original number. Local Optima: Make the current adjacent two digits satisfy monotonically increasing. |
| 968 | Binary Tree Cameras | Hard |
Although it is a binary tree, the minimum number of camera placements still follows the greedy approach. Trick: It is found that it is most cost-effective to place cameras on the parent nodes of leaf nodes and the child nodes of root nodes. However, you can only start traversing from one end. In comparison, it is more cost-effective to start traversing from leaf nodes (exponential growth), so we choose post-order for DFS.Global Optima: The minimum number of cameras used Local Optima: Let the parent node of the leaf node install a camera so that the minimum number of cameras is used. Tricky Part: Needs to come up with a solution for transferring the parent node camera coverage status through dfs parameter transfer. |