Greedy Algorithms
What is Greedy?
The essence of greedy is to choose the local optimum at each stage, aiming to achieve the global optimum.
Greedy Strategy
Try to find a counterexample; if none exists, then greedy is worth trying.
Steps
- Decompose the problem into subproblems.
- Find a suitable greedy strategy.
- Solve each subproblem optimally.
- Derive the global optimum from local optima.
Examples
1. Assign Cookies
Problem:
Assume you are a great parent wanting to give cookies to your children. Each child i has a greed factor g[i], which is the minimum size of a cookie that will satisfy that child. Each cookie j has a size s[j]. If s[j] >= g[i], you can assign cookie j to child i and the child will be satisfied. Your goal is to maximize the number of satisfied children and output that number.
Example 1:
Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The children's greed factors are 1, 2, and 3. Even though you have 2 cookies, both are size 1, so only the child with greed factor 1 can be satisfied. Hence, Output: 1.
Idea: Use the smallest cookie first to feed the least greedy child.
Solution:
class Solution {
public int findContentChildren(int[] g, int[] s) {
if (s.length == 0) return 0;
Arrays.sort(g);
Arrays.sort(s);
int count = 0;
// Feed the smallest greed first with smallest cookie
for (int i = 0; i < s.length && count < g.length; i++) {
if (s[i] >= g[count]) {
count++;
}
}
return count;
}
}
Summary: Think about local optimum, how to derive global optimum, and whether there exists a counterexample.
2. Wiggle Subsequence
Problem:
A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence. Given an integer array nums, return the length of the longest wiggle subsequence.
Example 1:
Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).
Idea: Include all peaks and valleys.
Solution:
class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length < 2) return nums.length;
int count = 1;
int prevDiff = 0;
for (int i = 1; i < nums.length; i++) {
int currDiff = nums[i] - nums[i-1];
if ((currDiff > 0 && prevDiff <= 0) || (currDiff < 0 && prevDiff >= 0)) {
count++;
prevDiff = currDiff;
}
}
return count;
}
}
Summary: The sequence should have the maximum number of peaks.
3. Maximum Subarray
Problem:
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Idea: Local optimum: if the current sum is negative, discard it and start from the next element. Global optimum: the maximum sum.
Solution:
class Solution {
public int maxSubArray(int[] nums) {
int maxSum = Integer.MIN_VALUE;
int currentSum = 0;
for (int num : nums) {
currentSum += num;
maxSum = Math.max(maxSum, currentSum);
if (currentSum < 0) currentSum = 0;
}
return maxSum;
}
}
4. Jump Game
Problem:
You are given an integer array nums. You are initially positioned at the array's first index, and each element represents your maximum jump length from that position. Return true if you can reach the last index, or false otherwise.
Idea: Expand the reachable range; if it covers the last index, return true.
Solution:
class Solution {
public boolean canJump(int[] nums) {
if (nums.length < 2) return true;
int maxReach = 0;
for (int i = 0; i <= maxReach; i++) {
maxReach = Math.max(maxReach, i + nums[i]);
if (maxReach >= nums.length - 1) return true;
}
return false;
}
}
Summary: Focus on coverage rather than individual jumps.
5. Jump Game II
Problem:
Given a 0-indexed array of integers nums of length n, you are initially positioned at nums[0]. Each element nums[i] represents the maximum jump length from index i. Return the minimum number of jumps to reach nums[n-1]. The test cases are generated such that you can always reach nums[n-1].
Idea: Jump to the farthest possible range each time; count how many times the range expands.
Solution:
class Solution {
public int jump(int[] nums) {
if (nums.length == 1) return 0;
int jumps = 0;
int currentEnd = 0;
int farthest = 0;
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == currentEnd) {
jumps++;
currentEnd = farthest;
}
}
return jumps;
}
}
6. Maximize Sum After K Negations
Problem:
Given an integer array nums and an integer k, modify the array by choosing an index i and replacing nums[i] with -nums[i]. Repeat this process exactly k times. You may choose the same index multiple times. Return the largest possible sum of the array after applying these changes.
Idea: First, flip the smallest negative numbers; if k remains, flip the smallest positive number (or zero) an even or odd number of times.
Solution:
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
Arrays.sort(nums);
for (int i = 0; i < nums.length && k > 0 && nums[i] < 0; i++, k--) {
nums[i] = -nums[i];
}
Arrays.sort(nums);
nums[0] = (k % 2 == 0) ? nums[0] : -nums[0];
int sum = 0;
for (int num : nums) sum += num;
return sum;
}
}
Summary: If there are negatives, flip those with largest absolute value; if no negatives, flip the smallest number.
7. Gas Station
Problem:
There are n gas stations along a circular route. You have a car with unlimited gas tank and it costs cost[i] to travel from station i to i+1. You begin with an empty tank. Given two integer arrays gas and cost, return the starting station's index if you can travel around the circuit once, otherwise return -1. If a solution exists, its guaranteed to be unique.
Idea: Traverse, accumulating gas[i] - cost[i]; if the sum becomes negative, reset start to next station.
Solution:
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int start = 0;
int currentTank = 0;
int totalTank = 0;
for (int i = 0; i < gas.length; i++) {
int diff = gas[i] - cost[i];
totalTank += diff;
currentTank += diff;
if (currentTank < 0) {
start = i + 1;
currentTank = 0;
}
}
return (totalTank < 0) ? -1 : start;
}
}
8. Candy Distribution
Problem:
There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings. You need to allocate candies to these children subject to the following requirements: each child must have at least one candy, and children with a higher rating than their neighbors get more candies. Return the minimum number of candies needed.
Idea: Consider two dimensions independently: left-to-right and right-to-left, then take the maximum of both.
Solution:
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
int[] left = new int[n];
int[] right = new int[n];
Arrays.fill(left, 1);
Arrays.fill(right, 1);
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i-1]) left[i] = left[i-1] + 1;
}
for (int i = n-2; i >= 0; i--) {
if (ratings[i] > ratings[i+1]) right[i] = right[i+1] + 1;
}
int total = 0;
for (int i = 0; i < n; i++) total += Math.max(left[i], right[i]);
return total;
}
}
9. Queue Reconstruction by Height
Problem:
You are given an array of people, people, each represented as [h_i, k_i]. This means the person has height h_i and exactly k_i people in front have a height greater than or equal to h_i. Reconstruct and return the queue.
Idea: Sort by height descending; for equal heights, sort by k ascending. Then insert each person at index k.
Solution:
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (a, b) -> {
if (a[0] == b[0]) return a[1] - b[1];
return b[0] - a[0];
});
List<int[]> result = new ArrayList<>();
for (int[] person : people) {
result.add(person[1], person);
}
return result.toArray(new int[result.size()][]);
}
}
Summary: When two dimensions are involved, determine one dimension first.
10. Minimum Number of Arrows to Burst Balloons
Problem:
There are some spherical balloons spread in two-dimensional space. Each balloon is represented as an interval [xstart, xend]. An arrow can be shot vertically from a point x. If xstart <= x <= xend, the balloon is burst. Return the minimum number of arrows needed to burst all balloons.
Idea: Sort by start ascending; if intervals overlap, use one arrow; otherwise, start a new arrow.
Solution:
class Solution {
public int findMinArrowShots(int[][] points) {
if (points.length == 0) return 0;
Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
int arrows = 1;
int currentEnd = points[0][1];
for (int i = 1; i < points.length; i++) {
if (points[i][0] <= currentEnd) {
currentEnd = Math.min(currentEnd, points[i][1]);
} else {
arrows++;
currentEnd = points[i][1];
}
}
return arrows;
}
}
11. Non-overlapping Intervals
Problem:
Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest non-overlapping.
Idea: Sort by start; if overlapping, remove the one with larger end (local optimum) and count.
Solution:
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
int count = 0;
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] < intervals[i-1][1]) {
intervals[i][1] = Math.min(intervals[i][1], intervals[i-1][1]);
count++;
}
}
return count;
}
}
12. Partition Labels
Problem:
You are given a string s. Partition the string into as many parts as possible so that each letter appears in at most one part. Return a list of integers representing the size of these parts.
Idea: Record the first and last occurrence of each letter; then merge intervals.
Solution:
class Solution {
public List<Integer> partitionLabels(String s) {
int[][] letters = new int[26][2];
for (int[] arr : letters) Arrays.fill(arr, -1);
for (int i = 0; i < s.length(); i++) {
int idx = s.charAt(i) - 'a';
if (letters[idx][0] == -1) letters[idx][0] = i;
letters[idx][1] = i;
}
Arrays.sort(letters, (a, b) -> Integer.compare(a[0], b[0]));
List<Integer> result = new ArrayList<>();
int start = 0, end = 0;
for (int[] letter : letters) {
if (letter[0] == -1) continue;
if (letter[0] <= end) {
end = Math.max(end, letter[1]);
} else {
result.add(end - start + 1);
start = letter[0];
end = letter[1];
}
}
result.add(end - start + 1);
return result;
}
}
13. Merge Intervals
Problem:
Given an array of intervals, merge all overlapping intervals and return an array of non-overlapping intervals.
Idea: Sort by start; merge overlapping intervals.
Solution:
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> result = new ArrayList<>();
int start = intervals[0][0];
int end = intervals[0][1];
for (int[] interval : intervals) {
if (interval[0] <= end) {
end = Math.max(end, interval[1]);
} else {
result.add(new int[]{start, end});
start = interval[0];
end = interval[1];
}
}
result.add(new int[]{start, end});
return result.toArray(new int[result.size()][]);
}
}
14. Monotone Increasing Digits
Problem:
Given a non-negative integer n, find the largest number less than or equal to n such that its digits are in non-decreasing order.
Idea: Traverse from right to left; if a digit is smaller than the previous, set that and all following digits to 9 and decrement the previous digit.
Solution:
class Solution {
public int monotoneIncreasingDigits(int n) {
char[] digits = String.valueOf(n).toCharArray();
int mark = digits.length;
for (int i = digits.length - 1; i > 0; i--) {
if (digits[i] < digits[i-1]) {
mark = i;
digits[i-1]--;
}
}
for (int i = mark; i < digits.length; i++) digits[i] = '9';
return Integer.parseInt(new String(digits));
}
}
15. Binary Tree Cameras
Problem:
Given a binary tree, install cameras on the nodes. Each camera can monitor its parent, itself, and its immediate children. Find the minimum number of cameras needed to monitor all nodes.
Idea: Traverse from leaves upward; assign states: -1: not covered, 0: covered, 1: camera installed.
Solution:
class Solution {
private int cameras = 0;
public int minCameraCover(TreeNode root) {
// If the root is not covered, add a camera
return (dfs(root) == -1) ? cameras + 1 : cameras;
}
private int dfs(TreeNode node) {
if (node == null) return 0; // covered by default
int left = dfs(node.left);
int right = dfs(node.right);
// If any child is not covered, place a camera here
if (left == -1 || right == -1) {
cameras++;
return 1; // camera installed
}
// If both children are covered, this node is not covered
if (left == 0 && right == 0) return -1;
// Otherwise, this node is covered by a child
return 0;
}
}
Summary: Local optimum: place cameras on parents of leaves. Global optimum: minimize total cameras.
To be continued...
