Greedy
Greedy algorithms make the locally optimal choice at each step, hoping to find the global optimum. Unlike dynamic programming, greedy doesn't reconsider past decisions. Greedy works when the problem has the greedy choice property (a locally optimal choice leads to a globally optimal solution) and optimal substructure. Proving a greedy approach is correct is often the hardest part.
When to Use
- →You need to maximize or minimize a value by making sequential choices
- →The locally optimal choice at each step leads to the global optimum
- →The problem involves scheduling, interval selection, or activity selection
- →A sorting step followed by a single scan can solve the problem
- →You need to determine if a goal is achievable by greedy extension (like jump game)
Approach
Greedy problems often start with sorting the input by some criterion. For interval scheduling, sort by end time and greedily select non-overlapping intervals. For the jump game, track the farthest reachable position and check if you can reach the end.
For maximum subarray (Kadane's algorithm), the greedy choice is: at each position, either extend the current subarray or start a new one. If the running sum becomes negative, it's always better to start fresh. This is greedy because you never look back.
The hardest part of greedy problems is convincing yourself (or the interviewer) that the greedy strategy is correct. One approach: assume there exists an optimal solution that makes a different choice at some step, and show you can swap in the greedy choice without making things worse (exchange argument).
Code Template
// Maximum subarray (Kadane's algorithm)
function maxSubArray(nums) {
let maxSum = nums[0];
let currentSum = nums[0];
for (let i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
// Jump game — can you reach the end?
function canJump(nums) {
let farthest = 0;
for (let i = 0; i < nums.length; i++) {
if (i > farthest) return false;
farthest = Math.max(farthest, i + nums[i]);
}
return true;
}
// Jump game II — minimum jumps to reach end
function jump(nums) {
let jumps = 0, currentEnd = 0, farthest = 0;
for (let i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i === currentEnd) {
jumps++;
currentEnd = farthest;
}
}
return jumps;
}