Contents

Greedy Algorithm Overview

Greedy algorithms make locally optimal choices at each step, hoping to find a global optimum. They work well when:

  • The problem has optimal substructure
  • The greedy choice property holds (locally optimal choice leads to global optimum)
  • No need to reconsider previous choices

Key Principles

  1. Greedy Choice Property: A global optimum can be reached by making locally optimal choices
  2. Optimal Substructure: Optimal solution contains optimal solutions to subproblems
  3. No Backtracking: Once a choice is made, it’s never reconsidered

Interval Scheduling

Greedy approach: Sort by end time, always pick the interval that ends earliest.

// Non-overlapping Intervals
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];  // Sort by end time
    });
    
    int count = 1;
    int end = intervals[0][1];
    
    for(int i = 1; i < intervals.size(); i++) {
        if(intervals[i][0] >= end) {
            count++;
            end = intervals[i][1];
        }
    }
    
    return intervals.size() - count;
}

Activity Selection

Similar to interval scheduling, select maximum number of non-overlapping activities.

// Maximum number of non-overlapping intervals
int maxNonOverlappingIntervals(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 count = 1;
    int end = intervals[0][1];
    
    for(int i = 1; i < intervals.size(); i++) {
        if(intervals[i][0] >= end) {
            count++;
            end = intervals[i][1];
        }
    }
    
    return count;
}

Fractional Knapsack

Greedy approach: Sort items by value/weight ratio, take items with highest ratio first.

// Fractional Knapsack (not a LeetCode problem, but classic greedy)
struct Item {
    int value, weight;
    double ratio;
};

double fractionalKnapsack(int W, vector<Item>& items) {
    sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return a.ratio > b.ratio;
    });
    
    double totalValue = 0.0;
    int remainingWeight = W;
    
    for(auto& item : items) {
        if(remainingWeight >= item.weight) {
            totalValue += item.value;
            remainingWeight -= item.weight;
        } else {
            totalValue += item.value * ((double)remainingWeight / item.weight);
            break;
        }
    }
    
    return totalValue;
}

Greedy on Arrays

Greedy choices on array elements, often with two pointers or sliding window.

// Maximum Subarray (Kadane's Algorithm)
int maxSubArray(vector<int>& nums) {
    int maxSum = nums[0];
    int currentSum = nums[0];
    
    for(int i = 1; i < nums.size(); i++) {
        currentSum = max(nums[i], currentSum + nums[i]);
        maxSum = max(maxSum, currentSum);
    }
    
    return maxSum;
}

// Best Time to Buy and Sell Stock II
int maxProfit(vector<int>& prices) {
    int profit = 0;
    for(int i = 1; i < prices.size(); i++) {
        if(prices[i] > prices[i-1]) {
            profit += prices[i] - prices[i-1];
        }
    }
    return profit;
}

// Candy - Greedy with sequence tracking
int candy(vector<int>& ratings) {
    const int N = ratings.size();
    int rtn = 1;
    int inc = 1, dec = 0, pre = 1;
    for(int i = 1; i < N; i++) {
        if(ratings[i] >= ratings[i - 1]) {
            dec = 0;
            pre = ratings[i] == ratings[i - 1] ? 1: pre + 1;
            rtn += pre;
            inc = pre;
        } else {
            dec++;
            if(dec == inc) {
                dec++;
            }
            rtn += dec;
            pre = 1;
        }
    }
    return rtn;
}

// Wiggle Subsequence - Greedy with difference tracking
int wiggleMaxLength(vector<int>& nums) {
    const int N = nums.size();
    if(N < 2) return N;
    int prevDiff = nums[1] - nums[0];
    int rtn = prevDiff != 0? 2 : 1;
    for(int i = 2; i < N; i++) {
        int diff = nums[i] - nums[i - 1];
        if((diff > 0 && prevDiff <= 0) ||
            diff < 0 && prevDiff >= 0) {
                rtn++;
                prevDiff = diff;
            }
    }
    return rtn;
}

Greedy on Strings

Greedy choices when processing strings, often with character frequency or ordering.

// Is Subsequence
bool isSubsequence(string s, string t) {
    int i = 0, j = 0;
    while(i < s.length() && j < t.length()) {
        if(s[i] == t[j]) {
            i++;
        }
        j++;
    }
    return i == s.length();
}

// Minimum Swaps to Make Strings Equal - Mismatch pairing
int minimumSwap(string s1, string s2) {
    int xy = 0, yx = 0;
    for(int i = 0; i < (int) s1.length(); i++) {
        if(s1[i] == 'x' && s2[i] == 'y') {
            xy++;
        } else if(s1[i] == 'y' && s2[i] == 'x') {
            yx++;
        }
    }
    if((xy + yx) % 2 == 1) {
        return -1;  // Impossible if odd total mismatches
    }
    return xy / 2 + yx / 2 + xy % 2 + yx % 2;
}

// Construct K Palindrome Strings - Frequency-based greedy
bool canConstruct(string s, int k) {
    int right = s.length();
    int occ[26] = {0};
    for(char ch: s) {
        occ[ch - 'a']++;
    }
    int left = 0;
    for(int i = 0; i < 26; i++) {
        if(occ[i] % 2 == 1) {
            left++;
        }
    }
    left = max(left, 1);
    return left <= k && k <= right;
}

Greedy with Sorting

Many greedy problems require sorting first to make optimal choices.

// Assign Cookies
int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    
    int i = 0, j = 0;
    int count = 0;
    
    while(i < g.size() && j < s.size()) {
        if(s[j] >= g[i]) {
            count++;
            i++;
        }
        j++;
    }
    
    return count;
}

// Array Partition - Maximize sum of minimums
int arrayPairSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int sum = 0;
    for(int i = 0; i < (int)nums.size(); i += 2) {
        sum += nums[i];
    }
    return sum;
}

// Maximum Units on a Truck - Fractional knapsack style
int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
    sort(boxTypes.begin(), boxTypes.end(), [](auto& u, auto& v){
        return u[1] > v[1];  // Sort by units per box (descending)
    });
    int remainSize = truckSize;
    int maximumUnits = 0;
    for(auto& boxType: boxTypes) {
        if(remainSize == 0) break;
        int cnt = min(remainSize, boxType[0]);
        maximumUnits += cnt * boxType[1];
        remainSize -= cnt;
    }
    return maximumUnits;
}

// Minimum Cost to Move Chips - Parity-based greedy
int minCostToMoveChips(vector<int>& position) {
    int even = 0, odd = 0;
    for(int pos : position) {
        if(pos % 2 == 0) {
            odd++;  // Count even positions
        } else {
            even++;  // Count odd positions
        }
    }
    return min(odd, even);  // Move minority parity to majority
}

// Two City Scheduling - Sort by cost difference
int twoCitySchedCost(vector<vector<int>>& costs) {
    sort(costs.begin(), costs.end(), [](auto& u, auto&v) {
        return (u[0] - u[1] < v[0] - v[1]);
    });
    int total = 0;
    const int N = costs.size() / 2;
    for(int i = 0; i < N; i++) {
        total += costs[i][0] + costs[i + N][1];
    }
    return total;
}

// Find Valid Matrix Given Row and Column Sums - Greedy two pointers
vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {
    const int N = rowSum.size(), M = colSum.size();
    vector<vector<int>> matrix(N, vector<int>(M, 0));
    int i = 0, j = 0;
    while(i < N && j < M) {
        int v = min(rowSum[i], colSum[j]);
        matrix[i][j] = v;
        rowSum[i] -= v;
        colSum[j] -= v;
        if(rowSum[i] == 0) i++;
        if(colSum[j] == 0) j++;
    }
    return matrix;
}

// Queue Reconstruction by Height
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];
    });
    
    vector<vector<int>> result;
    for(auto& person : people) {
        result.insert(result.begin() + person[1], person);
    }
    
    return result;
}

Easy Problems

ID Title Link Solution
455 Assign Cookies Link Solution
860 Lemonade Change Link Solution
392 Is Subsequence Link Solution
406 Queue Reconstruction by Height Link Solution
53 Maximum Subarray Link Solution
435 Non-overlapping Intervals Link Solution
452 Minimum Number of Arrows to Burst Balloons Link Solution
561 Array Partition Link Solution
1029 Two City Scheduling Link Solution
122 Best Time to Buy and Sell Stock II Link Solution
1710 Maximum Units on a Truck Link Solution
1217 Minimum Cost to Move Chips to The Same Position Link Solution

Medium Problems

ID Title Link Solution
763 Partition Labels Link -
621 Task Scheduler Link -
435 Non-overlapping Intervals Link Solution
55 Jump Game Link Solution
1094 Car Pooling Link Solution
45 Jump Game II Link Solution
134 Gas Station Link -
1024 Video Stitching Link -
1247 Minimum Swaps to Make Strings Equal Link Solution
1400 Construct K Palindrome Strings Link Solution
1605 Find Valid Matrix Given Row and Column Sums Link Solution
376 Wiggle Subsequence Link Solution

Hard Problems

ID Title Link Solution
135 Candy Link Solution
871 Minimum Number of Refueling Stops Link -
818 Race Car Link -
410 Split Array Largest Sum Link -
420 Strong Password Checker Link -
68 Text Justification Link -
76 Minimum Window Substring Link -
1799 Maximize Score After N Operations Link -

Common Greedy Patterns

1. Interval Problems

  • Sort by end time
  • Always pick the interval that ends earliest
  • Examples: Non-overlapping Intervals, Minimum Arrows to Burst Balloons

2. Two Pointers

  • Use two pointers to make greedy choices
  • Examples: Is Subsequence, Assign Cookies

3. Sorting + Greedy

  • Sort first, then apply greedy strategy
  • Examples: Queue Reconstruction by Height, Two City Scheduling

4. Local Optimization

  • Make best local choice at each step
  • Examples: Best Time to Buy and Sell Stock II, Maximum Subarray

5. Jump Problems

  • Greedy choice: jump as far as possible
  • Examples: Jump Game, Jump Game II

6. Scheduling Problems

  • Sort and schedule optimally
  • Examples: Task Scheduler, Car Pooling

Key Insights

  1. When to use Greedy:
    • Problem has optimal substructure
    • Greedy choice property holds
    • No need to reconsider previous choices
  2. Common Mistakes:
    • Not sorting when needed
    • Wrong sorting criteria
    • Not considering edge cases
    • Assuming greedy always works (need to prove correctness)
  3. Proving Greedy Correctness:
    • Show greedy choice property
    • Show optimal substructure
    • Use exchange argument or contradiction
  • Dynamic Programming (when greedy doesn’t work)
  • Sorting Algorithms
  • Interval Problems
  • Two Pointers
  • Sliding Window

References