Greedy Algorithms - Complete Guide

Greedy algorithms make locally optimal choices at each step to find a global optimum. This guide covers greedy strategies and classic problems.

What is a Greedy Algorithm? #

A greedy algorithm makes the best choice at each step without reconsidering previous choices. It builds up a solution piece by piece.

Key characteristics:

  1. Makes locally optimal choice
  2. Never reconsiders choices
  3. Hopes to find global optimum

When to use:

  • Optimization problems
  • When local optimum leads to global optimum
  • Proof of correctness exists

Classic Examples #

Activity Selection #

Select maximum number of non-overlapping activities.

function activitySelection(activities) {
  // Sort by end time
  activities.sort((a, b) => a.end - b.end);

  const selected = [activities[0]];
  let lastEnd = activities[0].end;

  for (let i = 1; i < activities.length; i++) {
    if (activities[i].start >= lastEnd) {
      selected.push(activities[i]);
      lastEnd = activities[i].end;
    }
  }

  return selected;
}

const activities = [
  { start: 1, end: 3 },
  { start: 2, end: 5 },
  { start: 4, end: 6 },
  { start: 6, end: 7 },
  { start: 5, end: 9 },
  { start: 8, end: 9 }
];

console.log(activitySelection(activities));
// [{ start: 1, end: 3 }, { start: 4, end: 6 }, { start: 6, end: 7 }, { start: 8, end: 9 }]

Fractional Knapsack #

Maximize value with fractional items.

function fractionalKnapsack(capacity, items) {
  // Sort by value/weight ratio
  items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));

  let totalValue = 0;
  let remaining = capacity;

  for (const item of items) {
    if (remaining >= item.weight) {
      // Take whole item
      totalValue += item.value;
      remaining -= item.weight;
    } else {
      // Take fraction
      totalValue += (remaining / item.weight) * item.value;
      break;
    }
  }

  return totalValue;
}

const items = [
  { weight: 10, value: 60 },
  { weight: 20, value: 100 },
  { weight: 30, value: 120 }
];

console.log(fractionalKnapsack(50, items));  // 240

Coin Change (Greedy) #

Find minimum coins for change (works for certain coin systems).

function coinChangeGreedy(coins, amount) {
  coins.sort((a, b) => b - a);

  let count = 0;

  for (const coin of coins) {
    while (amount >= coin) {
      amount -= coin;
      count++;
    }
  }

  return amount === 0 ? count : -1;
}

console.log(coinChangeGreedy([1, 5, 10, 25], 41));  // 5 (25 + 10 + 5 + 1)

// Note: Doesn't work for all coin systems
// Example: coins = [1, 3, 4], amount = 6
// Greedy: 4 + 1 + 1 = 3 coins
// Optimal: 3 + 3 = 2 coins

Jump Game #

Determine if you can reach the last index.

function canJump(nums) {
  let maxReach = 0;

  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) {
      return false;
    }

    maxReach = Math.max(maxReach, i + nums[i]);

    if (maxReach >= nums.length - 1) {
      return true;
    }
  }

  return true;
}

console.log(canJump([2, 3, 1, 1, 4]));  // true
console.log(canJump([3, 2, 1, 0, 4]));  // false

Jump Game II #

Find minimum jumps to reach end.

function minJumps(nums) {
  let jumps = 0;
  let currentEnd = 0;
  let 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;
}

console.log(minJumps([2, 3, 1, 1, 4]));  // 2
console.log(minJumps([2, 3, 0, 1, 4]));  // 2

Interval Problems #

Merge Intervals #

function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];

  intervals.sort((a, b) => a[0] - b[0]);

  const merged = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i];
    const last = merged[merged.length - 1];

    if (current[0] <= last[1]) {
      // Overlapping - merge
      last[1] = Math.max(last[1], current[1]);
    } else {
      // Non-overlapping - add new interval
      merged.push(current);
    }
  }

  return merged;
}

console.log(mergeIntervals([[1, 3], [2, 6], [8, 10], [15, 18]]));
// [[1, 6], [8, 10], [15, 18]]

Non-overlapping Intervals #

Remove minimum intervals to make rest non-overlapping.

function eraseOverlapIntervals(intervals) {
  if (intervals.length === 0) return 0;

  intervals.sort((a, b) => a[1] - b[1]);

  let count = 0;
  let end = intervals[0][1];

  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < end) {
      // Overlapping - remove current
      count++;
    } else {
      // Non-overlapping - update end
      end = intervals[i][1];
    }
  }

  return count;
}

console.log(eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]]));  // 1

Minimum Arrows #

Burst all balloons with minimum arrows.

function findMinArrowShots(points) {
  if (points.length === 0) return 0;

  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) {
      // Need new arrow
      arrows++;
      end = points[i][1];
    }
  }

  return arrows;
}

console.log(findMinArrowShots([[10, 16], [2, 8], [1, 6], [7, 12]]));  // 2

String Problems #

Remove K Digits #

Remove k digits to get smallest number.

function removeKdigits(num, k) {
  const stack = [];

  for (const digit of num) {
    while (k > 0 && stack.length > 0 && stack[stack.length - 1] > digit) {
      stack.pop();
      k--;
    }
    stack.push(digit);
  }

  // Remove remaining k digits from end
  while (k > 0) {
    stack.pop();
    k--;
  }

  // Remove leading zeros
  while (stack.length > 0 && stack[0] === '0') {
    stack.shift();
  }

  return stack.length === 0 ? '0' : stack.join('');
}

console.log(removeKdigits('1432219', 3));  // '1219'
console.log(removeKdigits('10200', 1));    // '200'

Partition Labels #

Partition string into as many parts as possible.

function partitionLabels(s) {
  const lastIndex = new Map();

  // Record last occurrence of each character
  for (let i = 0; i < s.length; i++) {
    lastIndex.set(s[i], i);
  }

  const result = [];
  let start = 0;
  let end = 0;

  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, lastIndex.get(s[i]));

    if (i === end) {
      result.push(end - start + 1);
      start = i + 1;
    }
  }

  return result;
}

console.log(partitionLabels('ababcbacadefegdehijhklij'));
// [9, 7, 8]

Reorganize String #

Rearrange string so no adjacent characters are same.

function reorganizeString(s) {
  const freq = new Map();

  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }

  // Sort by frequency
  const sorted = Array.from(freq.entries())
    .sort((a, b) => b[1] - a[1]);

  // Check if possible
  if (sorted[0][1] > Math.ceil(s.length / 2)) {
    return '';
  }

  const result = new Array(s.length);
  let index = 0;

  // Fill even positions first with most frequent
  for (const [char, count] of sorted) {
    for (let i = 0; i < count; i++) {
      if (index >= s.length) {
        index = 1;  // Start filling odd positions
      }
      result[index] = char;
      index += 2;
    }
  }

  return result.join('');
}

console.log(reorganizeString('aab'));   // 'aba'
console.log(reorganizeString('aaab'));  // ''

Array Problems #

Gas Station #

Find starting gas station to complete circuit.

function canCompleteCircuit(gas, cost) {
  let totalGas = 0;
  let currentGas = 0;
  let start = 0;

  for (let i = 0; i < gas.length; i++) {
    totalGas += gas[i] - cost[i];
    currentGas += gas[i] - cost[i];

    if (currentGas < 0) {
      start = i + 1;
      currentGas = 0;
    }
  }

  return totalGas >= 0 ? start : -1;
}

console.log(canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]));  // 3

Container With Most Water #

Find two lines that contain most water.

function maxArea(height) {
  let left = 0;
  let right = height.length - 1;
  let maxArea = 0;

  while (left < right) {
    const width = right - left;
    const h = Math.min(height[left], height[right]);
    maxArea = Math.max(maxArea, width * h);

    // Move pointer with smaller height
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }

  return maxArea;
}

console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]));  // 49

Best Time to Buy and Sell Stock #

Maximum profit from one transaction.

function maxProfit(prices) {
  let minPrice = Infinity;
  let maxProfit = 0;

  for (const price of prices) {
    minPrice = Math.min(minPrice, price);
    maxProfit = Math.max(maxProfit, price - minPrice);
  }

  return maxProfit;
}

console.log(maxProfit([7, 1, 5, 3, 6, 4]));  // 5

Best Time to Buy and Sell Stock II #

Maximum profit with multiple transactions.

function maxProfitII(prices) {
  let profit = 0;

  for (let i = 1; i < prices.length; i++) {
    if (prices[i] > prices[i - 1]) {
      profit += prices[i] - prices[i - 1];
    }
  }

  return profit;
}

console.log(maxProfitII([7, 1, 5, 3, 6, 4]));  // 7

Graph Problems #

Minimum Spanning Tree (Kruskal’s) #

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  union(x, y) {
    const px = this.find(x);
    const py = this.find(y);

    if (px === py) return false;

    if (this.rank[px] < this.rank[py]) {
      this.parent[px] = py;
    } else if (this.rank[px] > this.rank[py]) {
      this.parent[py] = px;
    } else {
      this.parent[py] = px;
      this.rank[px]++;
    }

    return true;
  }
}

function kruskalMST(n, edges) {
  edges.sort((a, b) => a[2] - b[2]);

  const uf = new UnionFind(n);
  const mst = [];
  let cost = 0;

  for (const [u, v, weight] of edges) {
    if (uf.union(u, v)) {
      mst.push([u, v, weight]);
      cost += weight;
    }
  }

  return { mst, cost };
}

const edges = [
  [0, 1, 10],
  [0, 2, 6],
  [0, 3, 5],
  [1, 3, 15],
  [2, 3, 4]
];

console.log(kruskalMST(4, edges));
// { mst: [[2,3,4], [0,3,5], [0,1,10]], cost: 19 }

Huffman Coding #

Optimal prefix-free encoding.

class HuffmanNode {
  constructor(char, freq) {
    this.char = char;
    this.freq = freq;
    this.left = null;
    this.right = null;
  }
}

function huffmanCoding(text) {
  const freq = new Map();

  for (const char of text) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }

  const minHeap = [];

  for (const [char, f] of freq) {
    minHeap.push(new HuffmanNode(char, f));
  }

  while (minHeap.length > 1) {
    minHeap.sort((a, b) => a.freq - b.freq);

    const left = minHeap.shift();
    const right = minHeap.shift();

    const parent = new HuffmanNode(null, left.freq + right.freq);
    parent.left = left;
    parent.right = right;

    minHeap.push(parent);
  }

  const codes = new Map();

  function generateCodes(node, code = '') {
    if (!node) return;

    if (node.char !== null) {
      codes.set(node.char, code);
      return;
    }

    generateCodes(node.left, code + '0');
    generateCodes(node.right, code + '1');
  }

  generateCodes(minHeap[0]);
  return codes;
}

const codes = huffmanCoding('hello world');
console.log(codes);

Greedy vs Dynamic Programming #

When Greedy Works:

  • Activity Selection
  • Fractional Knapsack
  • Huffman Coding
  • Minimum Spanning Tree

When DP Needed:

  • 0/1 Knapsack (can’t take fractions)
  • Longest Common Subsequence
  • Edit Distance
  • Coin Change (arbitrary coins)

Proving Correctness #

Greedy algorithms need proof of optimality.

Proof techniques:

  1. Exchange argument - Show greedy choice doesn’t prevent optimal solution
  2. Greedy stays ahead - Show greedy is always better or equal
  3. Induction - Prove optimal substructure

Best Practices #

  1. Sort first - Often needed for greedy choice
  2. Identify greedy choice - What makes choice optimal?
  3. Prove correctness - Counterexamples can disprove
  4. Consider alternatives - DP might be needed
  5. Edge cases - Empty input, single element
  6. Time complexity - Often O(n log n) from sorting

Greedy algorithms provide elegant solutions when local optimum leads to global optimum. Master the patterns to recognize when greedy works.

Previous Union Find (Disjoint Set) - Complete Guide Dynamic Programming - Complete Guide Next