Learn Greedy Introduction — Free DSA Tutorial

What is Greedy?

A greedy algorithm builds a solution step by step, always making whichever choice looks best right now, and never revisits or reconsiders that choice later — betting that a sequence of locally-best decisions adds up to a globally-best result.

Example: What is Greedy?

#include <iostream>
using namespace std;
int main() {
	cout << "Greedy: pick whichever choice looks best right now, never revisit that choice later";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Greedy: pick whichever choice looks best right now, never revisit that choice later");
	}
}

print("Greedy: pick whichever choice looks best right now, never revisit that choice later")

#include <stdio.h>
int main() {
	printf("Greedy: pick whichever choice looks best right now, never revisit that choice later");
	return 0;
}

Greedy Choice

A greedy choice is only trustworthy if it's provably safe — meaning some optimal solution is guaranteed to exist that agrees with this choice — since a greedy algorithm has no mechanism to undo a decision once it commits.

Example: Greedy Choice

#include <iostream>
using namespace std;
int main() {
	cout << "A greedy choice is trustworthy only if some optimal solution is provably guaranteed to agree with it";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("A greedy choice is trustworthy only if some optimal solution is provably guaranteed to agree with it");
	}
}

print("A greedy choice is trustworthy only if some optimal solution is provably guaranteed to agree with it")

#include <stdio.h>
int main() {
	printf("A greedy choice is trustworthy only if some optimal solution is provably guaranteed to agree with it");
	return 0;
}

Local Best

Depending on the problem, 'best right now' might mean the earliest deadline, the smallest weight, the largest value, or the highest profit-to-cost ratio — the specific rule always comes from proving what makes a choice safe for that particular problem.

Example: Local Best

#include <iostream>
using namespace std;
int main() {
	string rules[] = {"earliest deadline", "smallest weight", "largest value", "highest profit-to-cost ratio"};
	for (string r : rules) cout << r << "; ";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		String[] rules = {"earliest deadline", "smallest weight", "largest value", "highest profit-to-cost ratio"};
		for (String r : rules) System.out.print(r + "; ");
	}
}

rules = ["earliest deadline", "smallest weight", "largest value", "highest profit-to-cost ratio"]
print("; ".join(rules))

#include <stdio.h>
int main() {
	char* rules[] = {"earliest deadline", "smallest weight", "largest value", "highest profit-to-cost ratio"};
	for (int i = 0; i < 4; i++) printf("%s; ", rules[i]);
	return 0;
}

When Greedy Works

Greedy strategies only produce a correct answer for problems that actually have the right mathematical structure (often called the greedy-choice property and optimal substructure) — applying a greedy rule to a problem that lacks this structure can silently produce a wrong answer that looks plausible.

Example: When Greedy Works

#include <iostream>
using namespace std;
int main() {
	cout << "Requires greedy-choice property AND optimal substructure -- not every problem has this structure";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Requires greedy-choice property AND optimal substructure -- not every problem has this structure");
	}
}

print("Requires greedy-choice property AND optimal substructure -- not every problem has this structure")

#include <stdio.h>
int main() {
	printf("Requires greedy-choice property AND optimal substructure -- not every problem has this structure");
	return 0;
}

Practice

A good habit when facing a new optimization problem is to try small examples by hand, notice which local choice keeps producing the best outcome, and then try to prove that choice is always safe before trusting it in general.

Example: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Try small examples by hand, notice which local choice always wins, then try to prove it";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Try small examples by hand, notice which local choice always wins, then try to prove it");
	}
}

print("Try small examples by hand, notice which local choice always wins, then try to prove it")

#include <stdio.h>
int main() {
	printf("Try small examples by hand, notice which local choice always wins, then try to prove it");
	return 0;
}

Greedy Introduction

What is Greedy?

Greedy Choice

Local Best

When Greedy Works

Practice

Chapter Quiz — Complete all 5 topics to unlock

Login to run this code