Problems
Now that you’ve learned the greedy algorithm templates, it’s time to apply them to real coding challenges. This page contains carefully selected problems that will help you master greedy techniques and understand when to apply them.
Before starting: Make sure you’ve reviewed the Concept Guide to understand the theory and Code Templates for implementation patterns.
Recommended Study Order
Start with the Easy problems to build confidence, then progress through Medium to Hard. Each problem reinforces different aspects of greedy thinking.
Easy Problems
1. Maximum Subarray
- Brief: Find the contiguous subarray with the largest sum.
- Why this pattern?: At each step, decide whether to extend the current subarray or start a new one.
- Key Insight: Keep track of the maximum sum ending at the current position.
graph LR
A[Current Element] --> B{Extend or Restart?}
B -->|Extend| C[Add to current sum]
B -->|Restart| D[Start new sum]
C --> E[Update max if larger]
D --> E
E --> F[Move to next element]
function maxSubArray(nums) {
let maxSum = nums[0];
let currentSum = nums[0];
for (let i = 1; i < nums.length; i++) {
// Greedy choice: extend or restart
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}def maxSubArray(nums):
max_sum = current_sum = nums[0]
for num in nums[1:]:
# Greedy choice: extend or restart
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sumpublic int maxSubArray(int[] nums) {
int maxSum = nums[0];
int currentSum = nums[0];
for (int i = 1; i < nums.length; i++) {
// Greedy choice: extend or restart
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}int maxSubArray(vector<int>& nums) {
int maxSum = nums[0];
int currentSum = nums[0];
for (int i = 1; i < nums.size(); i++) {
// Greedy choice: extend or restart
currentSum = max(nums[i], currentSum + nums[i]);
maxSum = max(maxSum, currentSum);
}
return maxSum;
}func maxSubArray(nums []int) int {
maxSum := nums[0]
currentSum := nums[0]
for _, num := range nums[1:] {
// Greedy choice: extend or restart
if currentSum+num > num {
currentSum += num
} else {
currentSum = num
}
if currentSum > maxSum {
maxSum = currentSum
}
}
return maxSum
}def max_subarray(nums)
max_sum = current_sum = nums[0]
nums[1..-1].each do |num|
# Greedy choice: extend or restart
current_sum = [num, current_sum + num].max
max_sum = [max_sum, current_sum].max
end
max_sum
end2. Assign Cookies
- Brief: Assign cookies to children to maximize satisfied children.
- Why this pattern?: Always give the smallest cookie that satisfies the current child.
- Key Insight: Sort both arrays and use greedy matching.
graph TD
A[Sort children by greed] --> B[Sort cookies by size]
B --> C[For each child]
C --> D{Find smallest cookie >= greed}
D -->|Found| E[Assign cookie]
D -->|Not found| F[Skip child]
E --> G[Next child]
F --> G
function findContentChildren(g, s) {
g.sort((a, b) => a - b);
s.sort((a, b) => a - b);
let satisfied = 0;
let cookieIndex = 0;
for (let child of g) {
while (cookieIndex < s.length && s[cookieIndex] < child) {
cookieIndex++;
}
if (cookieIndex < s.length) {
satisfied++;
cookieIndex++;
}
}
return satisfied;
}def findContentChildren(g, s):
g.sort()
s.sort()
satisfied = 0
cookie_index = 0
for child in g:
while cookie_index < len(s) and s[cookie_index] < child:
cookie_index += 1
if cookie_index < len(s):
satisfied += 1
cookie_index += 1
return satisfiedpublic int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int satisfied = 0;
int cookieIndex = 0;
for (int child : g) {
while (cookieIndex < s.length && s[cookieIndex] < child) {
cookieIndex++;
}
if (cookieIndex < s.length) {
satisfied++;
cookieIndex++;
}
}
return satisfied;
}int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int satisfied = 0;
int cookieIndex = 0;
for (int child : g) {
while (cookieIndex < s.size() && s[cookieIndex] < child) {
cookieIndex++;
}
if (cookieIndex < s.size()) {
satisfied++;
cookieIndex++;
}
}
return satisfied;
}func findContentChildren(g, s []int) int {
sort.Ints(g)
sort.Ints(s)
satisfied := 0
cookieIndex := 0
for _, child := range g {
for cookieIndex < len(s) && s[cookieIndex] < child {
cookieIndex++
}
if cookieIndex < len(s) {
satisfied++
cookieIndex++
}
}
return satisfied
}def find_content_children(g, s)
g.sort!
s.sort!
satisfied = 0
cookie_index = 0
g.each do |child|
while cookie_index < s.length && s[cookie_index] < child
cookie_index += 1
end
if cookie_index < s.length
satisfied += 1
cookie_index += 1
end
end
satisfied
endMedium Problems
3. Minimum Number of Arrows to Burst Balloons
- Brief: Find minimum arrows to burst all balloons.
- Why this pattern?: Sort by end position and shoot when a balloon can’t be hit by the current arrow.
- Key Insight: Greedy choice is to shoot at the end of the current overlapping group.
graph TD
A[Sort balloons by end] --> B[Shoot at first end]
B --> C[Check next balloon]
C --> D{Start > current arrow?}
D -->|Yes| E[Shoot new arrow]
D -->|No| F[Continue]
E --> C
F --> C
function findMinArrowShots(points) {
if (points.length === 0) return 0;
// Sort by end position
points.sort((a, b) => a[1] - b[1]);
let arrows = 1;
let end = points[0][1];
for (let i = 1; i < points.length; i++) {
if (points[i][0] > end) {
arrows++;
end = points[i][1];
}
}
return arrows;
}def findMinArrowShots(points):
if not points:
return 0
# Sort by end position
points.sort(key=lambda x: x[1])
arrows = 1
end = points[0][1]
for start, point_end in points[1:]:
if start > end:
arrows += 1
end = point_end
return arrowspublic int findMinArrowShots(int[][] points) {
if (points.length == 0) return 0;
// Sort by end position
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
int arrows = 1;
int end = points[0][1];
for (int i = 1; i < points.length; i++) {
if (points[i][0] > end) {
arrows++;
end = points[i][1];
}
}
return arrows;
}int findMinArrowShots(vector<vector<int>>& points) {
if (points.empty()) return 0;
// Sort by end position
sort(points.begin(), points.end(), [](const auto& a, const auto& b) {
return a[1] < b[1];
});
int arrows = 1;
int end = points[0][1];
for (int i = 1; i < points.size(); i++) {
if (points[i][0] > end) {
arrows++;
end = points[i][1];
}
}
return arrows;
}func findMinArrowShots(points [][]int) int {
if len(points) == 0 {
return 0
}
// Sort by end position
sort.Slice(points, func(i, j int) bool {
return points[i][1] < points[j][1]
})
arrows := 1
end := points[0][1]
for i := 1; i < len(points); i++ {
if points[i][0] > end {
arrows++
end = points[i][1]
}
}
return arrows
}def find_min_arrow_shots(points)
return 0 if points.empty?
# Sort by end position
points.sort_by! { |point| point[1] }
arrows = 1
end_pos = points[0][1]
points[1..-1].each do |start, point_end|
if start > end_pos
arrows += 1
end_pos = point_end
end
end
arrows
end4. Task Scheduler
- Brief: Schedule tasks with cooldown periods to minimize total time.
- Why this pattern?: Always schedule the most frequent task first to maximize idle time utilization.
- Key Insight: The answer is either the total tasks or (max frequency - 1) * (cooldown + 1) + count of max frequency tasks.
Algorithm Flow:
1. Count task frequencies
A:3, B:2, C:1
2. Find max frequency
maxFreq = 3 (Task A)
3. Calculate idle slots needed
idleSlots = (maxFreq - 1) * n = (3-1) * 2 = 4
4. Fill with other tasks
Fill idle slots with remaining tasks
5. Return max(total tasks, calculated time)
Result = max(6, 8) = 8function leastInterval(tasks, n) {
const freq = new Array(26).fill(0);
for (let task of tasks) {
freq[task.charCodeAt(0) - 'A'.charCodeAt(0)]++;
}
freq.sort((a, b) => b - a);
const maxFreq = freq[0];
const idleTime = (maxFreq - 1) * n;
let idleSlots = idleTime;
for (let i = 1; i < 26 && freq[i] > 0; i++) {
idleSlots -= Math.min(freq[i], maxFreq - 1);
}
return Math.max(tasks.length, tasks.length + idleSlots);
}def leastInterval(tasks, n):
freq = [0] * 26
for task in tasks:
freq[ord(task) - ord('A')] += 1
freq.sort(reverse=True)
max_freq = freq[0]
idle_time = (max_freq - 1) * n
idle_slots = idle_time
for i in range(1, 26):
if freq[i] > 0:
idle_slots -= min(freq[i], max_freq - 1)
return max(len(tasks), len(tasks) + idle_slots)public int leastInterval(char[] tasks, int n) {
int[] freq = new int[26];
for (char task : tasks) {
freq[task - 'A']++;
}
Arrays.sort(freq);
int maxFreq = freq[25];
int idleTime = (maxFreq - 1) * n;
int idleSlots = idleTime;
for (int i = 24; i >= 0 && freq[i] > 0; i--) {
idleSlots -= Math.min(freq[i], maxFreq - 1);
}
return Math.max(tasks.length, tasks.length + idleSlots);
}int leastInterval(vector<char>& tasks, int n) {
vector<int> freq(26, 0);
for (char task : tasks) {
freq[task - 'A']++;
}
sort(freq.begin(), freq.end());
int maxFreq = freq[25];
int idleTime = (maxFreq - 1) * n;
int idleSlots = idleTime;
for (int i = 24; i >= 0 && freq[i] > 0; i--) {
idleSlots -= min(freq[i], maxFreq - 1);
}
return max((int)tasks.size(), (int)tasks.size() + idleSlots);
}func leastInterval(tasks []byte, n int) int {
freq := make([]int, 26)
for _, task := range tasks {
freq[task-'A']++
}
sort.Ints(freq)
maxFreq := freq[25]
idleTime := (maxFreq - 1) * n
idleSlots := idleTime
for i := 24; i >= 0 && freq[i] > 0; i-- {
idleSlots -= min(freq[i], maxFreq-1)
}
return max(len(tasks), len(tasks)+idleSlots)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}def least_interval(tasks, n)
freq = Array.new(26, 0)
tasks.each do |task|
freq[task.ord - 'A'.ord] += 1
end
freq.sort!
max_freq = freq[25]
idle_time = (max_freq - 1) * n
idle_slots = idle_time
(24.downto(0)).each do |i|
break if freq[i] == 0
idle_slots -= [freq[i], max_freq - 1].min
end
[tasks.length, tasks.length + idle_slots].max
endHard Problems
5. Remove Duplicate Letters
- Brief: Remove duplicate letters to get the smallest lexicographical result.
- Why this pattern?: At each position, choose the smallest possible character that still allows completing the string.
- Key Insight: Use a stack and greedy removal of larger characters when a smaller one appears later.
graph TD
A[Count character frequencies] --> B[Iterate through string]
B --> C{Current char < stack top?}
C -->|Yes and stack top appears later| D[Remove stack top]
C -->|No| E[Add to stack]
D --> C
E --> F[Mark as used]
F --> B
function removeDuplicateLetters(s) {
const freq = new Array(26).fill(0);
const used = new Array(26).fill(false);
const stack = [];
for (let char of s) {
freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
for (let char of s) {
const idx = char.charCodeAt(0) - 'a'.charCodeAt(0);
freq[idx]--;
if (used[idx]) continue;
while (stack.length > 0 &&
char < stack[stack.length - 1] &&
freq[stack[stack.length - 1].charCodeAt(0) - 'a'.charCodeAt(0)] > 0) {
const removed = stack.pop();
used[removed.charCodeAt(0) - 'a'.charCodeAt(0)] = false;
}
stack.push(char);
used[idx] = true;
}
return stack.join('');
}def removeDuplicateLetters(s):
freq = {}
used = set()
stack = []
for char in s:
freq[char] = freq.get(char, 0) + 1
for char in s:
freq[char] -= 1
if char in used:
continue
while (stack and char < stack[-1] and freq[stack[-1]] > 0):
removed = stack.pop()
used.remove(removed)
stack.append(char)
used.add(char)
return ''.join(stack)public String removeDuplicateLetters(String s) {
int[] freq = new int[26];
boolean[] used = new boolean[26];
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
freq[c - 'a']++;
}
for (char c : s.toCharArray()) {
freq[c - 'a']--;
if (used[c - 'a']) continue;
while (!stack.isEmpty() &&
c < stack.peek() &&
freq[stack.peek() - 'a'] > 0) {
char removed = stack.pop();
used[removed - 'a'] = false;
}
stack.push(c);
used[c - 'a'] = true;
}
StringBuilder sb = new StringBuilder();
for (char c : stack) {
sb.append(c);
}
return sb.toString();
}string removeDuplicateLetters(string s) {
vector<int> freq(26, 0);
vector<bool> used(26, false);
stack<char> st;
for (char c : s) {
freq[c - 'a']++;
}
for (char c : s) {
freq[c - 'a']--;
if (used[c - 'a']) continue;
while (!st.empty() &&
c < st.top() &&
freq[st.top() - 'a'] > 0) {
char removed = st.top();
st.pop();
used[removed - 'a'] = false;
}
st.push(c);
used[c - 'a'] = true;
}
string result;
while (!st.empty()) {
result = st.top() + result;
st.pop();
}
return result;
}func removeDuplicateLetters(s string) string {
freq := make([]int, 26)
used := make([]bool, 26)
var stack []rune
for _, char := range s {
freq[char-'a']++
}
for _, char := range s {
freq[char-'a']--
if used[char-'a'] {
continue
}
for len(stack) > 0 &&
char < stack[len(stack)-1] &&
freq[stack[len(stack)-1]-'a'] > 0 {
removed := stack[len(stack)-1]
stack = stack[:len(stack)-1]
used[removed-'a'] = false
}
stack = append(stack, char)
used[char-'a'] = true
}
return string(stack)
}def remove_duplicate_letters(s)
freq = Hash.new(0)
used = Set.new
stack = []
s.each_char { |char| freq[char] += 1 }
s.each_char do |char|
freq[char] -= 1
next if used.include?(char)
while (!stack.empty? &&
char < stack.last &&
freq[stack.last] > 0)
removed = stack.pop
used.delete(removed)
end
stack << char
used.add(char)
end
stack.join
end6. Create Maximum Number
- Brief: Create the maximum number from two arrays with a given length.
- Why this pattern?: For each possible split between arrays, greedily pick the largest available digits.
- Key Insight: Use monotonic stack to maintain largest sequence from each array, then merge optimally.
graph TD
A[For each possible split] --> B[Get max sequence from nums1]
A --> C[Get max sequence from nums2]
B --> D[Merge sequences optimally]
C --> D
D --> E[Track maximum result]
E --> F[Return best overall]
function maxNumber(nums1, nums2, k) {
function getMaxSequence(nums, k) {
const stack = [];
let drop = nums.length - k;
for (let num of nums) {
while (stack.length > 0 && num > stack[stack.length - 1] && drop > 0) {
stack.pop();
drop--;
}
stack.push(num);
}
return stack.slice(0, k);
}
function merge(nums1, nums2) {
const result = [];
let i = 0, j = 0;
while (i < nums1.length || j < nums2.length) {
if (compare(nums1, i, nums2, j)) {
result.push(nums1[i++]);
} else {
result.push(nums2[j++]);
}
}
return result;
}
function compare(nums1, i, nums2, j) {
while (i < nums1.length && j < nums2.length &&
nums1[i] === nums2[j]) {
i++;
j++;
}
return j === nums2.length || (i < nums1.length && nums1[i] > nums2[j]);
}
let result = [];
for (let i = Math.max(0, k - nums2.length); i <= Math.min(k, nums1.length); i++) {
const candidate = merge(
getMaxSequence(nums1, i),
getMaxSequence(nums2, k - i)
);
if (compare(candidate, 0, result, 0)) {
result = candidate;
}
}
return result;
}def maxNumber(nums1, nums2, k):
def getMaxSequence(nums, k):
stack = []
drop = len(nums) - k
for num in nums:
while stack and num > stack[-1] and drop > 0:
stack.pop()
drop -= 1
stack.append(num)
return stack[:k]
def merge(nums1, nums2):
result = []
i = j = 0
while i < len(nums1) or j < len(nums2):
if compare(nums1, i, nums2, j):
result.append(nums1[i])
i += 1
else:
result.append(nums2[j])
j += 1
return result
def compare(nums1, i, nums2, j):
while i < len(nums1) and j < len(nums2) and nums1[i] == nums2[j]:
i += 1
j += 1
return j == len(nums2) or (i < len(nums1) and nums1[i] > nums2[j])
result = []
for i in range(max(0, k - len(nums2)), min(k, len(nums1)) + 1):
candidate = merge(
getMaxSequence(nums1, i),
getMaxSequence(nums2, k - i)
)
if compare(candidate, 0, result, 0):
result = candidate
return resultpublic int[] maxNumber(int[] nums1, int[] nums2, int k) {
int[] result = new int[k];
for (int i = Math.max(0, k - nums2.length); i <= Math.min(k, nums1.length); i++) {
int[] candidate = merge(
getMaxSequence(nums1, i),
getMaxSequence(nums2, k - i)
);
if (compare(candidate, 0, result, 0)) {
result = candidate;
}
}
return result;
}
private int[] getMaxSequence(int[] nums, int k) {
int[] stack = new int[k];
int drop = nums.length - k;
int idx = 0;
for (int num : nums) {
while (idx > 0 && num > stack[idx - 1] && drop > 0) {
idx--;
drop--;
}
if (idx < k) {
stack[idx++] = num;
} else {
drop--;
}
}
return stack;
}
private int[] merge(int[] nums1, int[] nums2) {
int[] result = new int[nums1.length + nums2.length];
int i = 0, j = 0, k = 0;
while (i < nums1.length || j < nums2.length) {
if (compare(nums1, i, nums2, j)) {
result[k++] = nums1[i++];
} else {
result[k++] = nums2[j++];
}
}
return result;
}
private boolean compare(int[] nums1, int i, int[] nums2, int j) {
while (i < nums1.length && j < nums2.length && nums1[i] == nums2[j]) {
i++;
j++;
}
return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]);
}vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
vector<int> result(k);
for (int i = max(0, k - (int)nums2.size()); i <= min(k, (int)nums1.size()); i++) {
vector<int> candidate = merge(
getMaxSequence(nums1, i),
getMaxSequence(nums2, k - i)
);
if (compare(candidate, 0, result, 0)) {
result = candidate;
}
}
return result;
}
vector<int> getMaxSequence(vector<int>& nums, int k) {
vector<int> stack(k);
int drop = nums.size() - k;
int idx = 0;
for (int num : nums) {
while (idx > 0 && num > stack[idx - 1] && drop > 0) {
idx--;
drop--;
}
if (idx < k) {
stack[idx++] = num;
} else {
drop--;
}
}
return stack;
}
vector<int> merge(vector<int>& nums1, vector<int>& nums2) {
vector<int> result(nums1.size() + nums2.size());
int i = 0, j = 0, k = 0;
while (i < nums1.size() || j < nums2.size()) {
if (compare(nums1, i, nums2, j)) {
result[k++] = nums1[i++];
} else {
result[k++] = nums2[j++];
}
}
return result;
}
bool compare(vector<int>& nums1, int i, vector<int>& nums2, int j) {
while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j]) {
i++;
j++;
}
return j == nums2.size() || (i < nums1.size() && nums1[i] > nums2[j]);
}func maxNumber(nums1 []int, nums2 []int, k int) []int {
result := make([]int, k)
for i := max(0, k-len(nums2)); i <= min(k, len(nums1)); i++ {
candidate := merge(
getMaxSequence(nums1, i),
getMaxSequence(nums2, k-i),
)
if compare(candidate, 0, result, 0) {
copy(result, candidate)
}
}
return result
}
func getMaxSequence(nums []int, k int) []int {
stack := make([]int, k)
drop := len(nums) - k
idx := 0
for _, num := range nums {
for idx > 0 && num > stack[idx-1] && drop > 0 {
idx--
drop--
}
if idx < k {
stack[idx] = num
idx++
} else {
drop--
}
}
return stack
}
func merge(nums1, nums2 []int) []int {
result := make([]int, len(nums1)+len(nums2))
i, j, k := 0, 0, 0
for i < len(nums1) || j < len(nums2) {
if compare(nums1, i, nums2, j) {
result[k] = nums1[i]
i++
} else {
result[k] = nums2[j]
j++
}
k++
}
return result
}
func compare(nums1 []int, i int, nums2 []int, j int) bool {
for i < len(nums1) && j < len(nums2) && nums1[i] == nums2[j] {
i++
j++
}
return j == len(nums2) || (i < len(nums1) && nums1[i] > nums2[j])
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}def max_number(nums1, nums2, k)
result = []
(max(0, k - nums2.length)..min(k, nums1.length)).each do |i|
candidate = merge(
get_max_sequence(nums1, i),
get_max_sequence(nums2, k - i)
)
if compare(candidate, 0, result, 0)
result = candidate
end
end
result
end
def get_max_sequence(nums, k)
stack = []
drop = nums.length - k
nums.each do |num|
while !stack.empty? && num > stack.last && drop > 0
stack.pop
drop -= 1
end
stack << num if stack.length < k
end
stack
end
def merge(nums1, nums2)
result = []
i = j = 0
while i < nums1.length || j < nums2.length
if compare(nums1, i, nums2, j)
result << nums1[i]
i += 1
else
result << nums2[j]
j += 1
end
end
result
end
def compare(nums1, i, nums2, j)
while i < nums1.length && j < nums2.length && nums1[i] == nums2[j]
i += 1
j += 1
end
j == nums2.length || (i < nums1.length && nums1[i] > nums2[j])
end
def min(a, b)
a < b ? a : b
end
def max(a, b)
a > b ? a : b
endStudy Tips
- Start Simple: Begin with Easy problems to build intuition
- Understand the Greedy Choice: For each problem, identify what makes the greedy choice optimal
- Practice Proofs: Try to prove why the greedy approach works for each problem
- Edge Cases: Pay attention to empty inputs, single elements, and boundary conditions
- Time Complexity: Always analyze the time and space complexity of your solutions
Remember: Greedy algorithms are elegant but require careful analysis. Always verify that the greedy choice property holds before implementing!