Greedy Algorithm Principles and Problem Solving Patterns
Core Concepts
The fundamental idea behind greedy algorithms is making the locally optimal choice at each stage with the hope of finding a global optimum. For instance, if given a stack of banknotes and allowed to pick ten, selecting the highest denomination each time ensures the maximum total value. This local maximization leads to the global solution.
However, this approach does not work for all problems. Consider packing a backpack with a volume limit; choosing the largest items first might prevent fitting more smaller items that yield a better total value. Such scenarios typically require dynamic programming.
Strategy Identification
There is no fixed template for greedy algorithms. The challenge lies in proving that local optimal choices lead to a global optimum. This often requires manual simulation or mathematical proof. If simulation suggests the strategy works, its worth implementing; otherwise, dynamic programming might be necessary.
Implementation Workflow
- Decompose the problem into smaller sub-problems.
- Identify a suitable greedy strategy.
- Solve each sub-problem optimally.
- Combine local solutions to form the global result.
In practice, strictly following these steps is less common than simply identifying the local optimal condition and verifying if it yields the global optimum.
Common Problem Patterns
Assign Cookies
Strategy: Satisfy children with smaller appetites first using the smallest available cookies.
class Solution {
public:
int findContentChildren(vector<int>& appetites, vector<int>& cookieSizes) {
std::sort(appetites.begin(), appetites.end());
std::sort(cookieSizes.begin(), cookieSizes.end());
int satisfiedCount = 0;
for (int cookieIdx = 0; cookieIdx < cookieSizes.size() && satisfiedCount < appetites.size(); ++cookieIdx) {
if (cookieSizes[cookieIdx] >= appetites[satisfiedCount]) {
satisfiedCount++;
}
}
return satisfiedCount;
}
};
Wiggle Subsequence
Strategy: Count peaks and valleys by tracking the difference between consecutive elements.
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() < 2) return nums.size();
int peaks = 1;
int prevDiff = 0;
for (size_t i = 1; i < nums.size(); ++i) {
int diff = nums[i] - nums[i - 1];
if ((diff > 0 && prevDiff <= 0) || (diff < 0 && prevDiff >= 0)) {
peaks++;
prevDiff = diff;
}
}
return peaks;
}
};
Maximum Subarray Sum
Strategy: Reset the current sum if it becomes negative, as a negative prefix reduces the total.
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxSum = INT_MIN;
int currentSum = 0;
for (int val : nums) {
currentSum += val;
if (currentSum > maxSum) {
maxSum = currentSum;
}
if (currentSum <= 0) {
currentSum = 0;
}
}
return maxSum;
}
};
Best Time to Buy and Sell Stock II
Strategy: Accumulate all positive profit differences between consecutive days.
class Solution {
public:
int maxProfit(vector<int>& prices) {
int totalProfit = 0;
for (size_t i = 1; i < prices.size(); ++i) {
int diff = prices[i] - prices[i - 1];
if (diff > 0) {
totalProfit += diff;
}
}
return totalProfit;
}
};
Jump Game
Strategy: Track the maximum reachable index. If the current index exceeds the max reach, the end is unreachable.
class Solution {
public:
bool canJump(vector<int>& nums) {
int maxReach = 0;
for (int i = 0; i <= maxReach && i < nums.size(); ++i) {
maxReach = max(maxReach, i + nums[i]);
if (maxReach >= nums.size() - 1) return true;
}
return false;
}
};
Jump Game II
Strategy: Track the current range end and the farthest reachable point. Increment steps when the current range is exhausted.
class Solution {
public:
int jump(vector<int>& nums) {
if (nums.size() <= 1) return 0;
int steps = 0;
int currentEnd = 0;
int farthest = 0;
for (int i = 0; i < nums.size() - 1; ++i) {
farthest = max(farthest, i + nums[i]);
if (i == currentEnd) {
steps++;
currentEnd = farthest;
if (currentEnd >= nums.size() - 1) break;
}
}
return steps;
}
};
Maximize Sum Of Array After K Negations
Strategy: Flip negative numbers to positive starting from the smallest. If operations remain, flip the smallest absolute value.
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() && k > 0; ++i) {
if (nums[i] < 0) {
nums[i] = -nums[i];
k--;
} else {
break;
}
}
std::sort(nums.begin(), nums.end());
if (k % 2 == 1) {
nums[0] = -nums[0];
}
return accumulate(nums.begin(), nums.end(), 0);
}
};
Gas Station
Strategy: If the total gas is less than total cost, no solution exists. Otherwise, reset the start point when ever the current tank drops below zero.
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int totalSurplus = 0;
int currentSurplus = 0;
int startPoint = 0;
for (size_t i = 0; i < gas.size(); ++i) {
int net = gas[i] - cost[i];
totalSurplus += net;
currentSurplus += net;
if (currentSurplus < 0) {
startPoint = i + 1;
currentSurplus = 0;
}
}
return totalSurplus < 0 ? -1 : startPoint;
}
};
Candy
Strategy: Two passes: left-to-right to satisfy increasing ratings, then right-to-left to satisfy decreasing ratings.
class Solution {
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
vector<int> candies(n, 1);
for (int i = 1; i < n; ++i) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
for (int i = n - 2; i >= 0; --i) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = max(candies[i], candies[i + 1] + 1);
}
}
return accumulate(candies.begin(), candies.end(), 0);
}
};
Lemonade Change
Strategy: Track $5 and $10 bills. Prioritize giving $10 + $5 for $20 change to preserve $5 bills.
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int fiveCount = 0;
int tenCount = 0;
for (int bill : bills) {
if (bill == 5) {
fiveCount++;
} else if (bill == 10) {
if (fiveCount > 0) {
fiveCount--;
tenCount++;
} else {
return false;
}
} else {
if (tenCount > 0 && fiveCount > 0) {
tenCount--;
fiveCount--;
} else if (fiveCount >= 3) {
fiveCount -= 3;
} else {
return false;
}
}
}
return true;
}
};
Reconstruct Queue by Height
Strategy: Sort by height descending, then by k ascending. Insert each person at index k.
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
});
list<vector<int>> queue;
for (const auto& person : people) {
auto it = queue.begin();
advance(it, person[1]);
queue.insert(it, person);
}
return vector<vector<int>>(queue.begin(), queue.end());
}
};
Minimum Number of Arrows to Burst Balloons
Strategy: Sort by end coordinate. Merge overlapping intervals to minimize arrows.
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
if (points.empty()) return 0;
sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
return a[1] < b[1];
});
int arrows = 1;
int currentEnd = points[0][1];
for (size_t i = 1; i < points.size(); ++i) {
if (points[i][0] > currentEnd) {
arrows++;
currentEnd = points[i][1];
}
}
return arrows;
}
};
Non-overlapping Intervals
Strategy: Sort by end coordinate. Count overlaps and remove the interval ending later.
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) return 0;
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
return a[1] < b[1];
});
int removed = 0;
int prevEnd = intervals[0][1];
for (size_t i = 1; i < intervals.size(); ++i) {
if (intervals[i][0] < prevEnd) {
removed++;
} else {
prevEnd = intervals[i][1];
}
}
return removed;
}
};
Partition Labels
Strategy: Record the last occurrence of each character. Extend the partition until the current index matches the max last occurrence.
class Solution {
public:
vector<int> partitionLabels(string s) {
vector<int> lastOccurrence(26, 0);
for (int i = 0; i < s.size(); ++i) {
lastOccurrence[s[i] - 'a'] = i;
}
vector<int> result;
int start = 0;
int end = 0;
for (int i = 0; i < s.size(); ++i) {
end = max(end, lastOccurrence[s[i] - 'a']);
if (i == end) {
result.push_back(i - start + 1);
start = i + 1;
}
}
return result;
}
};
Merge Intervals
Strategy: Sort by start time. Merge overlapping intervals by updating the end time.
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) return {};
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
merged.push_back(intervals[0]);
for (size_t i = 1; i < intervals.size(); ++i) {
vector<int>& last = merged.back();
if (intervals[i][0] <= last[1]) {
last[1] = max(last[1], intervals[i][1]);
} else {
merged.push_back(intervals[i]);
}
}
return merged;
}
};
Monotone Increasing Digits
Strategy: Find the first decrease, decrement the previous digit, and set all subsequent digits to 9.
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string s = to_string(n);
int marker = s.size();
for (int i = s.size() - 1; i > 0; --i) {
if (s[i - 1] > s[i]) {
marker = i;
s[i - 1]--;
}
}
for (int i = marker; i < s.size(); ++i) {
s[i] = '9';
}
return stoi(s);
}
};
Binary Tree Cameras
Strategy: Post-order traversal. States: 0 (Needs Camera), 1 (Has Camera), 2 (Covered). Install camera if a child needs it.
class Solution {
public:
int cameras = 0;
int traverse(TreeNode* node) {
if (!node) return 2;
int left = traverse(node->left);
int right = traverse(node->right);
if (left == 0 || right == 0) {
cameras++;
return 1;
}
if (left == 1 || right == 1) {
return 2;
}
return 0;
}
int minCameraCover(TreeNode* root) {
if (traverse(root) == 0) cameras++;
return cameras;
}
};
