Blog

Greedy Algorithms with Java

Greedy Algorithms with Java are a brilliant approach to solving optimisation problems, so understanding them is crucial. They can address issues like resource allocation and pathfinding with efficiency. Dive into this fascinating world to see how these algorithms can become a powerful tool in your coding arsenal. Curious yet? Keep reading!

What is ‘Greedy Algorithms with Java’?

A greedy algorithm builds a solution step by step, choosing the option that looks best at each stage, aiming for the overall optimum

Optimal Substructure and Greedy Choice Property:

  • Optimal Substructure: A problem has this property if its optimal solution contains optimal solutions to its subproblems.
  • Greedy Choice Property: A problem satisfies this if a locally optimal choice at each step leads to a globally optimal solution.

Pros:

  • Simple to design and implement
  • Fast and efficient for suitable problems
  • Requires less memory than other methods

Cons:

  • Doesn’t always guarantee the best global solution
  • Only works if both properties are satisfied
  • May require proof of correctness before use

Greedy Algorithm in Java: Step-by-Step Example

Example: Activity Selection Problem in Java

The Activity Selection Problem aims to select the maximum number of activities that don’t overlap, given their start and finish times.

Java Code

import java.util.Arrays;
import java.util.Comparator;

class Activity {
    int start, finish;
    Activity(int start, int finish) {
        this.start = start;
        this.finish = finish;
    }
}

public class ActivitySelection {
    public static void main(String[] args) {
        Activity[] activities = {
            new Activity(1, 3),
            new Activity(2, 5),
            new Activity(4, 6),
            new Activity(6, 8),
            new Activity(5, 7),
            new Activity(8, 9)
        };

        // Sort activities by finish time
        Arrays.sort(activities, Comparator.comparingInt(a -> a.finish));

        System.out.println("Selected Activities:");
        int lastFinishTime = -1;
        for (Activity activity : activities) {
            if (activity.start >= lastFinishTime) {
                System.out.println("(" + activity.start + ", " + activity.finish + ")");
                lastFinishTime = activity.finish;
            }
        }
    }
}

Explanation:

  1. We create an Activity class with start and finish times.
  2. Activities are sorted by their finish time.
  3. We iterate and pick each activity if it starts after or at the last selected activity’s finish time.

Output:

Selected Activities:
(1, 3)
(4, 6)
(6, 8)
(8, 9)

Advanced Examples of Greedy Algorithms in Java

1. Huffman Coding in Java

What it is:
Huffman Coding is a greedy algorithm for lossless data compression. It assigns shorter codes to more frequent characters and longer codes to less frequent ones.

Java Code

import java.util.PriorityQueue;

class HuffmanNode {
    int data;
    char c;
    HuffmanNode left, right;
}

class MyComparator implements java.util.Comparator<HuffmanNode> {
    public int compare(HuffmanNode x, HuffmanNode y) {
        return x.data - y.data;
    }
}

public class HuffmanCoding {
    public static void printCode(HuffmanNode root, String s) {
        if (root.left == null && root.right == null && Character.isLetter(root.c)) {
            System.out.println(root.c + ": " + s);
            return;
        }
        printCode(root.left, s + "0");
        printCode(root.right, s + "1");
    }

    public static void main(String[] args) {
        int n = 6;
        char[] charArray = { 'a', 'b', 'c', 'd', 'e', 'f' };
        int[] charfreq = { 5, 9, 12, 13, 16, 45 };

        PriorityQueue<HuffmanNode> q = new PriorityQueue<>(n, new MyComparator());

        for (int i = 0; i < n; i++) {
            HuffmanNode hn = new HuffmanNode();
            hn.c = charArray[i];
            hn.data = charfreq[i];
            hn.left = null;
            hn.right = null;
            q.add(hn);
        }

        while (q.size() > 1) {
            HuffmanNode x = q.poll();
            HuffmanNode y = q.poll();
            HuffmanNode f = new HuffmanNode();
            f.data = x.data + y.data;
            f.c = '-';
            f.left = x;
            f.right = y;
            q.add(f);
        }

        printCode(q.peek(), "");
    }
}

Explanation:

  1. Create nodes for each character and frequency.
  2. Build a min-heap (priority queue) based on frequency.
  3. Extract two smallest nodes, merge them, and reinsert until one root remains.
  4. Traverse tree to generate binary codes.

Output:

f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111

2. Kruskal’s Algorithm in Java

What it is:
Kruskal’s algorithm finds a Minimum Spanning Tree (MST) for a weighted undirected graph by picking edges with the smallest weights first.

Java Code

import java.util.*;

class Edge implements Comparable<Edge> {
    int src, dest, weight;
    public int compareTo(Edge compareEdge) {
        return this.weight - compareEdge.weight;
    }
}

class Subset {
    int parent, rank;
}

public class Kruskal {
    int vertices, edges;
    Edge[] edge;

    Kruskal(int v, int e) {
        vertices = v;
        edges = e;
        edge = new Edge[e];
        for (int i = 0; i < e; i++) {
            edge[i] = new Edge();
        }
    }

    int find(Subset[] subsets, int i) {
        if (subsets[i].parent != i)
            subsets[i].parent = find(subsets, subsets[i].parent);
        return subsets[i].parent;
    }

    void union(Subset[] subsets, int x, int y) {
        int xroot = find(subsets, x);
        int yroot = find(subsets, y);
        if (subsets[xroot].rank < subsets[yroot].rank)
            subsets[xroot].parent = yroot;
        else if (subsets[xroot].rank > subsets[yroot].rank)
            subsets[yroot].parent = xroot;
        else {
            subsets[yroot].parent = xroot;
            subsets[xroot].rank++;
        }
    }

    void kruskalMST() {
        Edge[] result = new Edge[vertices];
        int e = 0;
        int i = 0;
        for (i = 0; i < vertices; ++i)
            result[i] = new Edge();

        Arrays.sort(edge);

        Subset[] subsets = new Subset[vertices];
        for (i = 0; i < vertices; ++i) {
            subsets[i] = new Subset();
            subsets[i].parent = i;
            subsets[i].rank = 0;
        }

        i = 0;
        while (e < vertices - 1) {
            Edge next_edge = edge[i++];
            int x = find(subsets, next_edge.src);
            int y = find(subsets, next_edge.dest);

            if (x != y) {
                result[e++] = next_edge;
                union(subsets, x, y);
            }
        }

        System.out.println("Edges in the constructed MST:");
        for (i = 0; i < e; ++i)
            System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
    }

    public static void main(String[] args) {
        int V = 4;
        int E = 5;
        Kruskal graph = new Kruskal(V, E);

        graph.edge[0].src = 0;
        graph.edge[0].dest = 1;
        graph.edge[0].weight = 10;

        graph.edge[1].src = 0;
        graph.edge[1].dest = 2;
        graph.edge[1].weight = 6;

        graph.edge[2].src = 0;
        graph.edge[2].dest = 3;
        graph.edge[2].weight = 5;

        graph.edge[3].src = 1;
        graph.edge[3].dest = 3;
        graph.edge[3].weight = 15;

        graph.edge[4].src = 2;
        graph.edge[4].dest = 3;
        graph.edge[4].weight = 4;

        graph.kruskalMST();
    }
}

Explanation:

  1. Sort all edges by weight.
  2. Pick the smallest edge and check if it forms a cycle using Union-Find.
  3. If not, add it to MST.
  4. Repeat until MST contains V-1 edges.

Output:

Edges in the constructed MST:
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10

Common Pitfalls & Best Practices in Greedy Algorithms in Java

When Greedy Algorithms in Java Fail

Greedy algorithms in java fail when a local optimum choice doesn’t lead to the global optimum. This happens when:

  • The problem doesn’t satisfy Optimal Substructure or Greedy Choice Property.
  • Future decisions are heavily affected by earlier choices, making a “short-term best” choice suboptimal.
  • The solution space is large and requires backtracking or dynamic programming.

Example of failure:

  • Coin change problem with denominations {1, 3, 4} and target 6.
    • Greedy picks 4 + 1 + 1 (3 coins),
    • Optimal is 3 + 3 (2 coins).

How to Check if a Greedy Approach Will Work

  1. Test the Greedy Choice Property – Check if choosing the locally optimal solution always leads to a global optimum.
  2. Check Optimal Substructure – See if optimal solutions can be constructed from optimal subproblem solutions.
  3. Mathematical Proof – Use induction or contradiction to prove correctness.
  4. Compare with Dynamic Programming – Solve small cases with both approaches to verify correctness.

Real-World Applications of Greedy Algorithms in Java

1. Coin Change Problem

Real-life use:

  • Google Pay & Paytm use similar logic when breaking down transactions into available denomination notes or coins for cash withdrawal machines.

Java Code

import java.util.Arrays;

public class CoinChangeGreedy {
    public static void main(String[] args) {
        int[] coins = {10, 5, 2, 1};
        int amount = 27;

        Arrays.sort(coins);
        int n = coins.length;
        int count = 0;

        System.out.print("Coins used: ");
        for (int i = n - 1; i >= 0; i--) {
            while (amount >= coins[i]) {
                amount -= coins[i];
                System.out.print(coins[i] + " ");
                count++;
            }
        }
        System.out.println("\nTotal coins used: " + count);
    }
}

Output:

Coins used: 10 10 5 2 
Total coins used: 4

2. Activity Selection Problem

Real-life use:

  • Google Calendar uses a similar concept for auto-scheduling events without overlaps.

(Code already provided in earlier section)

3. Huffman Coding

Real-life use:

  • Gmail and WhatsApp use Huffman coding internally in data compression for faster message and attachment transfer.

(Code already provided in earlier section)

4. Minimum Spanning Tree (Prim’s and Kruskal’s Algorithm)

Real-life use:

  • Facebook uses MST logic for network optimization, such as finding the minimum connection path between servers in their data centers.
  • Google Maps uses MST in some cases for road network optimizations.

Prim’s Algorithm in Java

import java.util.*;

public class PrimsAlgorithm {
    public static void main(String[] args) {
        int V = 5;
        int[][] graph = {
            {0, 2, 0, 6, 0},
            {2, 0, 3, 8, 5},
            {0, 3, 0, 0, 7},
            {6, 8, 0, 0, 9},
            {0, 5, 7, 9, 0}
        };

        primMST(graph, V);
    }

    static void primMST(int[][] graph, int V) {
        int[] key = new int[V];
        int[] parent = new int[V];
        boolean[] mstSet = new boolean[V];

        Arrays.fill(key, Integer.MAX_VALUE);
        key[0] = 0;
        parent[0] = -1;

        for (int count = 0; count < V - 1; count++) {
            int u = minKey(key, mstSet, V);
            mstSet[u] = true;

            for (int v = 0; v < V; v++) {
                if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u][v];
                }
            }
        }

        System.out.println("Edge \tWeight");
        for (int i = 1; i < V; i++)
            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
    }

    static int minKey(int[] key, boolean[] mstSet, int V) {
        int min = Integer.MAX_VALUE, minIndex = -1;
        for (int v = 0; v < V; v++) {
            if (!mstSet[v] && key[v] < min) {
                min = key[v];
                minIndex = v;
            }
        }
        return minIndex;
    }
}

Output:

Edge    Weight
0 - 1   2
1 - 2   3
0 - 3   6
1 - 4   5

Greedy Algorithms Interview


  1. What is a greedy algorithm?
    Greedy algorithms make the locally optimal choice at each stage with the intention of finding a global optimum. It’s like choosing the best immediate move without always examining wider consequences.

  2. Why would you use a greedy algorithm?
    They’re used when a problem can be solved by making a sequence of choices, each of which looks the best at that moment, mainly due to their simplicity and speed.

  3. Can you name an example where a greedy algorithm is effective?
    One popular example is the “activity selection” problem, where the goal is to select the maximum number of activities that don’t overlap.

  4. What are the limitations of greedy algorithms?
    They don’t always produce the globally optimal solution. For these cases, other methods like dynamic programming may be more suitable.

  5. How does a greedy approach differ from dynamic programming?
    While greedy algorithms make a series of local decisions, dynamic programming solves problems by combining solutions to sub-problems. It often considers more extensive scenarios.

Our AI-powered java online compiler makes coding a breeze, letting users instantly write, run, and test their code. It’s seamless and efficient, leveraging AI to offer real-time feedback and error checks. Embrace innovation and elevate your coding with this cutting-edge compiler today!

Conclusion

‘Greedy Algorithms with Java’ offers a robust understanding of efficient problem-solving techniques. Completing it gives you confidence in tackling complex projects with ease. Dive deeper into programming by exploring resources at Newtum and feel the rewarding sense of becoming a proficient coder.

Edited and Compiled by

This article was compiled and edited by @rasikadeshpande, who has over 4 years of experience in writing. She’s passionate about helping beginners understand technical topics in a more interactive way.

About The Author

Sagar Salunkhe

See author's posts