Why Greedy Works and When It Fails in DSA Java - Why This Pattern

Mental Model

Greedy picks the best choice right now hoping it leads to the best overall result. Sometimes this works perfectly, sometimes it misses better options later.

Analogy: Imagine choosing snacks from a buffet by always picking the tastiest-looking item first. Sometimes you get the best meal, but other times you miss a better combo if you planned ahead.

Choices: [5] -> [3] -> [8] -> [2] -> null
Greedy picks the biggest number at each step.

Dry Run Walkthrough

Input: Array: [5, 3, 8, 2], goal: select numbers to maximize sum by picking locally best choices

Goal: Show how greedy picks the biggest number each time and when it works or fails

Step 1: Pick the biggest number first: 8

Selected: 8, Remaining: [5, 3, 2]

Why: Greedy chooses the largest immediate value to maximize sum

Step 2: Next pick biggest from remaining: 5

Selected: 8 -> 5, Remaining: [3, 2]

Why: Greedy continues picking locally best choices

Step 3: Pick next biggest: 3

Selected: 8 -> 5 -> 3, Remaining: [2]

Why: Greedy keeps choosing the largest available

Step 4: Pick last number: 2

Selected: 8 -> 5 -> 3 -> 2, Remaining: []

Why: All numbers selected, greedy finished

Result:

Selected: 8 -> 5 -> 3 -> 2, Sum = 18
Greedy works here because picking largest each time maximizes sum.

Annotated Code

DSA Java

import java.util.*;

public class GreedyExample {
    // Greedy picks largest number each time
    public static List<Integer> greedyPick(int[] arr) {
        List<Integer> selected = new ArrayList<>();
        boolean[] used = new boolean[arr.length];
        for (int i = 0; i < arr.length; i++) {
            int maxIndex = -1;
            int maxVal = Integer.MIN_VALUE;
            // Find largest unused number
            for (int j = 0; j < arr.length; j++) {
                if (!used[j] && arr[j] > maxVal) {
                    maxVal = arr[j];
                    maxIndex = j;
                }
            }
            if (maxIndex != -1) {
                used[maxIndex] = true; // mark chosen
                selected.add(arr[maxIndex]);
            }
        }
        return selected;
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 2};
        List<Integer> result = greedyPick(arr);
        int sum = 0;
        for (int num : result) {
            System.out.print(num + " -> ");
            sum += num;
        }
        System.out.println("null");
        System.out.println("Sum = " + sum);
    }
}

for (int i = 0; i < arr.length; i++) {

repeat selection for each element to pick the largest unused number

for (int j = 0; j < arr.length; j++) { if (!used[j] && arr[j] > maxVal) { maxVal = arr[j]; maxIndex = j; } }

find the largest unused number in the array

used[maxIndex] = true; selected.add(arr[maxIndex]);

mark the chosen number as used and add to selected list

Output

8 -> 5 -> 3 -> 2 -> null

Sum = 18

Complexity Analysis

Time: O(n^2) because for each of n picks we scan the array to find the max unused element

Space: O(n) for storing the selected elements and used flags

vs Alternative: Compared to sorting once (O(n log n)) and picking in order, this repeated scanning is less efficient but illustrates greedy choice clearly

Edge Cases

Empty array

Returns empty selection without error

DSA Java

for (int i = 0; i < arr.length; i++) {

All elements equal

Picks all elements in original order since all have same value

DSA Java

if (!used[j] && arr[j] > maxVal)

Single element array

Picks the single element correctly

DSA Java

for (int i = 0; i < arr.length; i++) {

When to Use This Pattern

When a problem asks to make a sequence of choices to optimize a total and local best choices seem promising, try greedy to see if picking the best immediate option leads to global best.

Common Mistakes

Mistake: Assuming greedy always finds the best overall solution
Fix: Check if problem has overlapping subproblems or requires backtracking; greedy only works when local best choices lead to global best

Summary

Greedy picks the best immediate choice hoping it leads to the best overall result.

Use greedy when local optimal choices guarantee global optimal solution.

The key insight is that greedy works only if local best choices never block better future options.

Practice

1. What is the main reason a greedy algorithm works correctly for some problems?

easy

A. Because it uses recursion to explore all paths

B. Because it tries all possible solutions and picks the best

C. Because it makes the best choice at each step hoping for a global optimum

D. Because it sorts the input data before processing

Solution

1. Step 1: Understand greedy choice property

   A greedy algorithm chooses the best option available at each step without reconsidering previous choices.

2. Step 2: Connect greedy choice to global optimum

   This local best choice leads to a global optimum only if the problem has the greedy choice property.

3. Final Answer:

   Because it makes the best choice at each step hoping for a global optimum -> Option C

4. Quick Check:

   Greedy choice property = Because it makes the best choice at each step hoping for a global optimum [OK]

Hint: Greedy picks best now, not all possibilities [OK]

Common Mistakes:

• Thinking greedy tries all solutions
• Confusing greedy with recursion
• Assuming sorting alone makes greedy correct

2. Which of the following is the correct syntax to start a greedy algorithm loop in Java to process an array arr of length n?

easy

A. foreach (int i : arr)

B. for i in range(0, n):

C. while (i <= n) { i++; }

D. for (int i = 0; i < n; i++)

Solution

1. Step 1: Identify Java loop syntax

   Java uses for loops with initialization, condition, and increment: for (int i = 0; i < n; i++)

2. Step 2: Check options for Java correctness

   for (int i = 0; i < n; i++) matches Java syntax; B is Python, C is incomplete and incorrect, D is incorrect syntax for array iteration.

3. Final Answer:

   for (int i = 0; i < n; i++) -> Option D

4. Quick Check:

   Java for loop syntax = for (int i = 0; i < n; i++) [OK]

Hint: Java for loops use int i=0; i

Common Mistakes:

• Using Python syntax in Java
• Incorrect loop conditions
• Misusing foreach syntax

3. Consider the following Java code snippet for selecting intervals greedily by earliest finish time:

int[][] intervals = {{1,3},{2,5},{4,7}};
Arrays.sort(intervals, (a,b) -> a[1] - b[1]);
int count = 0, end = 0;
for (int[] interval : intervals) {
  if (interval[0] >= end) {
    count++;
    end = interval[1];
  }
}
System.out.println(count);

What is the output?

medium

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Sort intervals by finish time

   Sorted intervals by end time: {1,3}, {2,5}, {4,7}

2. Step 2: Select intervals greedily

   Select {1,3} first (count=1, end=3). Next {2,5} starts at 2 < 3, skip. Next {4,7} starts at 4 >= 3, select (count=2).

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Greedy interval selection = 2 [OK]

Hint: Pick intervals by earliest finish time [OK]

Common Mistakes:

• Not sorting intervals
• Selecting overlapping intervals
• Counting all intervals without check

4. The following Java code attempts to solve the coin change problem using a greedy approach:

int[] coins = {1, 3, 4};
int amount = 6;
int count = 0;
for (int i = coins.length - 1; i >= 0; i--) {
  while (amount >= coins[i]) {
    amount -= coins[i];
    count++;
  }
}
System.out.println(count);

What is the output and what is the problem with this approach?

medium

A. 3; Greedy fails because it doesn't find minimum coins

B. 3; Greedy always finds minimum coins

C. 6; Code has syntax error

D. 0; Code does not run

Solution

1. Step 1: Trace greedy coin selection

   Start with coin 4: amount=6>=4, subtract 4 (amount=2), count=1. Next coin 3: amount=2<3 skip. Next coin 1: amount=2>=1 subtract twice, count=3 total coins.

2. Step 2: Check minimum coins possible

   Minimum coins for 6 are 2 (3+3), but greedy picks 3 coins (4+1+1). Greedy fails here.

3. Final Answer:

   3; Greedy fails because it doesn't find minimum coins -> Option A

4. Quick Check:

   Greedy coin change fails = 3; Greedy fails because it doesn't find minimum coins [OK]

Hint: Greedy may fail if coin set is non-canonical [OK]

Common Mistakes:

• Assuming greedy always finds minimum coins
• Ignoring coin order importance
• Confusing output count with amount

5. You want to schedule the maximum number of non-overlapping meetings in one room. Meetings are given as int[][] meetings = {{0, 30}, {5, 10}, {15, 20}, {25, 35}}. Which greedy strategy will always give the optimal solution and why?

hard

A. Select meetings by earliest finish time because it leaves room for more meetings

B. Select meetings by shortest duration because shorter meetings fit more

C. Select meetings by latest start time because it prioritizes recent meetings

D. Select meetings by earliest start time because it schedules more meetings

Solution

1. Step 1: Understand meeting scheduling problem

   Goal is to maximize non-overlapping meetings in one room.

2. Step 2: Analyze greedy strategies

   Choosing earliest finish time frees room earliest, allowing more meetings after.

3. Step 3: Check other strategies

   Earliest start or shortest duration can cause overlaps or miss optimal sets.

4. Final Answer:

   Select meetings by earliest finish time because it leaves room for more meetings -> Option A

5. Quick Check:

   Earliest finish time = optimal scheduling [OK]

Hint: Pick meetings finishing earliest to fit more [OK]

Common Mistakes:

• Choosing earliest start time
• Picking shortest duration meetings
• Ignoring finish times