Greedy Algorithms in Java: Common LeetCode Patterns
2025-08-13
Greedy algorithms pick the locally best move at each step and never look back. They work when local choices can be proven to lead to a global optimum. In interviews, your job is to spot when a greedy choice is safe, explain why, and code a clean solution.
This guide gives you the patterns that show up most on LeetCode, with short Java snippets and talking points you can use in an interview.
How to know a greedy solution is safe
Use one of these arguments to justify your choice:
-
Exchange argument
Show that any optimal solution can be transformed into one that makes your greedy choice first without getting worse.
-
Stays optimal under prefixes
After each step, the subproblem that remains is the same kind of problem. Your choice does not reduce future options in a harmful way.
-
Matroid like structure
Feasible sets closed under taking subsets with a natural notion of “best next item.” You do not need to say “matroid” in an interview, just say why picking the best next item cannot block a better full solution.
Pattern 1: Interval scheduling by earliest finish
Task: maximum number of non overlapping intervals.
Greedy rule: sort by end time and always take the interval that finishes earliest.
import java.util.*;
public class MaxNonOverlappingIntervals {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) return 0;
Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
int count = 0, end = Integer.MIN_VALUE;
for (int[] iv : intervals) {
if (iv[0] >= end) { // take it
count++;
end = iv[1];
}
}
return intervals.length - count; // removals to make non overlapping
}
}
Why it works: exchange argument. If an optimal solution takes a later finishing interval when an earlier finishing one also fits, swapping never hurts and may only help.
Pattern 2: Merge intervals
Task: merge all overlapping intervals.
Greedy rule: sort by start and extend the current merged interval as far as possible.
import java.util.*;
public class MergeIntervals {
public int[][] merge(int[][] a) {
if (a.length == 0) return a;
Arrays.sort(a, Comparator.comparingInt(iv -> iv[0]));
List<int[]> res = new ArrayList<>();
int[] cur = a[0].clone();
for (int i = 1; i < a.length; i++) {
if (a[i][0] <= cur[1]) cur[1] = Math.max(cur[1], a[i][1]);
else { res.add(cur); cur = a[i].clone(); }
}
res.add(cur);
return res.toArray(new int[res.size()][]);
}
}
Why: once intervals are sorted by start, the only greedy decision is whether to extend or start a new block.
Pattern 3: Minimum arrows to burst balloons
Task: each balloon is an interval. Shoot as few arrows as possible so each arrow position hits all intervals covering it.
Greedy rule: sort by end and shoot at the current end.
import java.util.*;
public class MinArrows {
public int findMinArrowShots(int[][] points) {
Arrays.sort(points, Comparator.comparingLong(p -> (long)p[1]));
int arrows = 0;
long pos = Long.MIN_VALUE;
for (int[] p : points) {
if (pos < p[0]) { // need new arrow
arrows++;
pos = p[1];
}
}
return arrows;
}
}
Pattern 4: Jump Game (reachability)
Task: given max jump lengths, can you reach the end.
Greedy rule: track the farthest index you can reach so far.
public class JumpGame {
public boolean canJump(int[] nums) {
int far = 0;
for (int i = 0; i <= far && i < nums.length; i++) {
far = Math.max(far, i + nums[i]);
}
return far >= nums.length - 1;
}
}
Why: prefix optimality. If index i is reachable, the best we can do after processing i is the max of previous far and i + nums[i].
Pattern 5: Jump Game II (fewest jumps)
Task: minimum number of jumps to reach the end.
Greedy rule: expand a level of reach, then jump when you finish the current level.
public class JumpGameII {
public int jump(int[] nums) {
int jumps = 0, curEnd = 0, far = 0;
for (int i = 0; i < nums.length - 1; i++) {
far = Math.max(far, i + nums[i]);
if (i == curEnd) {
jumps++;
curEnd = far;
}
}
return jumps;
}
}
Pattern 6: Gas Station
Task: find a start index to complete the circuit once, or report none.
Greedy rule: if a partial route fails at j, any start between the last start and j also fails. Skip ahead.
public class GasStation {
public int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
int net = gas[i] - cost[i];
total += net;
tank += net;
if (tank < 0) { // cannot reach i + 1 from current start
start = i + 1;
tank = 0;
}
}
return total >= 0 ? start : -1;
}
}
Why: if you go negative at i, every start in the current segment is invalid. Jump the start past i.
Pattern 7: Assign Cookies
Task: each child has greed factor, each cookie has size. Maximize satisfied children.
Greedy rule: sort both. Give the smallest cookie that fits the current smallest child.
import java.util.*;
public class AssignCookies {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int i = 0, j = 0, n = g.length, m = s.length;
while (i < n && j < m) {
if (s[j] >= g[i]) { i++; j++; } else { j++; }
}
return i;
}
}
Pattern 8: Partition Labels
Task: split a string so each letter appears in at most one part. Return sizes.
Greedy rule: expand current partition to the farthest last occurrence of any character you saw.
import java.util.*;
public class PartitionLabels {
public List<Integer> partitionLabels(String s) {
int[] last = new int[26];
for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;
List<Integer> res = new ArrayList<>();
int end = 0, size = 0;
for (int i = 0; i < s.length(); i++) {
end = Math.max(end, last[s.charAt(i) - 'a']);
size++;
if (i == end) { res.add(size); size = 0; }
}
return res;
}
}
Pattern 9: Candy
Task: ratings array, give candies so higher rated kids get more than neighbors. Minimize total.
Greedy rule: two passes. Left to right then right to left, take the max needed from both sides.
import java.util.*;
public class Candy {
public int candy(int[] ratings) {
int n = ratings.length;
int[] left = new int[n];
Arrays.fill(left, 1);
for (int i = 1; i < n; i++)
if (ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
int right = 1, total = Math.max(left[n - 1], 1);
for (int i = n - 2; i >= 0; i--) {
right = ratings[i] > ratings[i + 1] ? right + 1 : 1;
total += Math.max(left[i], right);
}
return total;
}
}
Why: local constraints only involve neighbors. Greedy on both sides satisfies both inequalities.
Pattern 10: Minimum number of platforms or rooms
Task: classic Meeting Rooms II or Train Platforms.
Greedy rule: sweep line with sorted starts and ends.
import java.util.*;
public class MinRooms {
public int minMeetingRooms(int[][] intervals) {
int n = intervals.length;
int[] starts = new int[n], ends = new int[n];
for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; }
Arrays.sort(starts);
Arrays.sort(ends);
int rooms = 0, j = 0;
for (int i = 0; i < n; i++) {
if (starts[i] < ends[j]) rooms++;
else j++;
}
return rooms;
}
}
Pattern 11: Maximum units on a truck
Task: each box type has count and units per box. Capacity is limited. Maximize units.
Greedy rule: take highest unit value first.
import java.util.*;
public class MaxUnits {
public int maximumUnits(int[][] types, int cap) {
Arrays.sort(types, (a,b) -> Integer.compare(b[1], a[1]));
int units = 0;
for (int[] t : types) {
int take = Math.min(cap, t[0]);
units += take * t[1];
cap -= take;
if (cap == 0) break;
}
return units;
}
}
Pattern 12: Activity selection with profits can break greedy
Coin change caution: taking largest coin first only works for canonical systems like US coins. For arbitrary coin sets, greedy can fail. If the problem smells like knapsack or requires exact sums with odd coin sets, switch to DP. Mention this to score points.
Interview checklist
- What is the natural score or priority for each item
- Can I sort by a single key that supports an exchange argument
- After one greedy step, is the remaining subproblem the same kind
- Can I prove local choice is safe with a short swap argument
- What is the time complexity after sorting
- Any counterexample where greedy fails. If yes, pivot to DP
Quick practice set
- Non overlapping intervals
- Jump Game I and II
- Gas Station
- Assign Cookies
- Partition Labels
- Candy
- Minimum arrows to burst balloons
- Minimum platforms or Meeting Rooms II
- Maximum units on a truck
Work through these and you will build a strong instinct for when greedy applies.
If you want a lightweight way to compare your idea to a clean greedy outline while practicing, you can use a helper that sits off your screen share and shows the exact rule plus a short proof sketch. It lets you keep moving instead of stalling.
Try StealthCoder when you want a fast explanation and working code to study during practice: https://stealthcoder.app