Greedy Algorithms

Greedy algorithms are a class of algorithms that make locally optimal choices at each step with the hope of finding a global optimum. They are particularly useful for optimization problems where a series of choices lead to the best solution.

Table of Contents

• Table of Contents
• Greedy Algorithm Basics
• Common Greedy Patterns
  • 1. Activity Selection
  • 2. Fractional Knapsack
  • 3. Huffman Coding
  • 4. Minimum Spanning Tree (Kruskal’s Algorithm)
• Time and Space Complexity
• Related Leetcode Questions
  • Easy
  • Medium
  • Hard

Greedy Algorithm Basics

• Definition: A greedy algorithm makes the locally optimal choice at each step with the hope of finding the global optimum.
• Key Characteristics:
  • Greedy Choice Property: A global optimum can be arrived at by selecting a local optimum.
  • Optimal Substructure: An optimal solution to the problem contains optimal solutions to subproblems.
• Example: Coin Change problem where you want to make change with the fewest number of coins.

  public int coinChange(int[] coins, int amount) {
      Arrays.sort(coins);
      int count = 0;
      for (int i = coins.length - 1; i >= 0; i--) {
          while (amount >= coins[i]) {
              amount -= coins[i];
              count++;
          }
      }
      return amount == 0 ? count : -1;
  }

• Time Complexity: O(n log n) (due to sorting)
• Space Complexity: O(1)

Common Greedy Patterns

1. Activity Selection

• Problem: Select the maximum number of activities that don’t overlap.
• Example:

  public int activitySelection(int[] start, int[] end) {
      int n = start.length;
      int[][] activities = new int[n][2];
      for (int i = 0; i < n; i++) {
          activities[i][0] = start[i];
          activities[i][1] = end[i];
      }
      Arrays.sort(activities, (a, b) -> a[1] - b[1]);
      int count = 1;
      int lastEnd = activities[0][1];
      for (int i = 1; i < n; i++) {
          if (activities[i][0] >= lastEnd) {
              count++;
              lastEnd = activities[i][1];
          }
      }
      return count;
  }

• Time Complexity: O(n log n) (due to sorting)
• Space Complexity: O(n)

2. Fractional Knapsack

• Problem: Given weights and values of items, determine the maximum value that can be carried in a knapsack of a given capacity, where items can be broken into fractions.
• Example:

  public double fractionalKnapsack(int[] weights, int[] values, int capacity) {
      int n = weights.length;
      double[][] items = new double[n][2];
      for (int i = 0; i < n; i++) {
          items[i][0] = weights[i];
          items[i][1] = values[i];
      }
      Arrays.sort(items, (a, b) -> Double.compare(b[1] / b[0], a[1] / a[0]));
      double totalValue = 0;
      for (int i = 0; i < n; i++) {
          if (capacity >= items[i][0]) {
              capacity -= items[i][0];
              totalValue += items[i][1];
          } else {
              totalValue += (capacity / items[i][0]) * items[i][1];
              break;
          }
      }
      return totalValue;
  }

• Time Complexity: O(n log n) (due to sorting)
• Space Complexity: O(n)

3. Huffman Coding

• Problem: Construct a prefix code (Huffman code) for a given set of characters with their frequencies.
• Example:

  public class HuffmanNode implements Comparable<HuffmanNode> {
      int freq;
      char data;
      HuffmanNode left, right;
      HuffmanNode(char data, int freq) {
          this.data = data;
          this.freq = freq;
      }
      public int compareTo(HuffmanNode node) {
          return this.freq - node.freq;
      }
  }
  public HuffmanNode buildHuffmanTree(char[] data, int[] freq) {
      PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();
      for (int i = 0; i < data.length; i++) {
          pq.add(new HuffmanNode(data[i], freq[i]));
      }
      while (pq.size() > 1) {
          HuffmanNode left = pq.poll();
          HuffmanNode right = pq.poll();
          HuffmanNode parent = new HuffmanNode('\0', left.freq + right.freq);
          parent.left = left;
          parent.right = right;
          pq.add(parent);
      }
      return pq.poll();
  }

• Time Complexity: O(n log n) (due to priority queue operations)
• Space Complexity: O(n)

4. Minimum Spanning Tree (Kruskal’s Algorithm)

• Problem: Find the minimum spanning tree for a weighted undirected graph.
• Example:

  public int kruskalMST(int[][] edges, int V) {
      Arrays.sort(edges, (a, b) -> a[2] - b[2]);
      int[] parent = new int[V];
      Arrays.fill(parent, -1);
      int totalWeight = 0;
      for (int[] edge : edges) {
          int u = edge[0], v = edge[1], w = edge[2];
          int setU = find(parent, u);
          int setV = find(parent, v);
          if (setU != setV) {
              totalWeight += w;
              union(parent, setU, setV);
          }
      }
      return totalWeight;
  }
  private int find(int[] parent, int i) {
      if (parent[i] == -1) {
          return i;
      }
      return find(parent, parent[i]);
  }
  private void union(int[] parent, int x, int y) {
      int setX = find(parent, x);
      int setY = find(parent, y);
      parent[setX] = setY;
  }

• Time Complexity: O(E log E) or O(E log V)
• Space Complexity: O(V)

Time and Space Complexity

Problem	Time Complexity	Space Complexity
Activity Selection	O(n log n)	O(n)
Fractional Knapsack	O(n log n)	O(n)
Huffman Coding	O(n log n)	O(n)
Kruskal’s Algorithm	O(E log E)	O(V)

Related Leetcode Questions

Easy

1. Assign Cookies
2. Lemonade Change
3. Best Time to Buy and Sell Stock II

Medium

1. Jump Game
2. Gas Station
3. Minimum Number of Arrows to Burst Balloons

Hard

1. Candy
2. IPO
3. Task Scheduler