Greedy Algorithms Pattern

Greedy Algorithms make locally optimal choices at each step with the hope of finding a global optimum. They don't reconsider previous choices and work well for optimization problems with certain properties.

When to Use This Pattern

  • Problems with optimal substructure
  • Problems with greedy choice property
  • Interval scheduling problems
  • Activity selection problems
  • Minimum spanning tree problems
  • Shortest path problems (Dijkstra's)

Key Concepts

Greedy Choice Property

A global optimum can be reached by making locally optimal choices. The choice made at each step is the best choice at that moment.

Optimal Substructure

An optimal solution contains optimal solutions to subproblems. This is similar to dynamic programming, but greedy algorithms don't store solutions to subproblems.

Algorithm Section

General Greedy Template

function greedy(problem):
    solution = []
    
    while problem is not solved:
        choice = makeGreedyChoice(problem)
        if choice is valid:
            solution.add(choice)
            problem = updateProblem(problem, choice)
    
    return solution

Activity Selection Example

def activitySelection(activities):
    # Sort by finish time
    activities.sort(key=lambda x: x[1])
    
    selected = [activities[0]]
    last_finish = activities[0][1]
    
    for start, finish in activities[1:]:
        if start >= last_finish:
            selected.append((start, finish))
            last_finish = finish
    
    return selected

Practice Problems

Problem 1: Jump Game (LeetCode #55)

You are given an integer array nums. You are initially positioned at the array's first index, and each element represents your maximum jump length. Return true if you can reach the last index.

Solution:

def canJump(nums):
    max_reach = 0
    
    for i in range(len(nums)):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + nums[i])
        if max_reach >= len(nums) - 1:
            return True
    
    return True

Explanation: We greedily track the maximum position we can reach. At each step, we update max_reach to be the maximum of current max_reach and the position we can reach from current index. If we can't reach current index (i > max_reach), return False. If max_reach >= last index, return True.

Time Complexity: O(n)

Space Complexity: O(1)

Problem 2: Merge Intervals (LeetCode #56)

Given an array of intervals, merge all overlapping intervals.

Solution:

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    
    for current in intervals[1:]:
        last = merged[-1]
        if current[0] <= last[1]:
            last[1] = max(last[1], current[1])
        else:
            merged.append(current)
    
    return merged

Explanation: Sort intervals by start time. Greedily merge overlapping intervals. If current interval overlaps with last merged interval (current.start <= last.end), merge by updating the end. Otherwise, add as new interval.

Time Complexity: O(n log n)

Space Complexity: O(n)

Problem 3: Non-overlapping Intervals (LeetCode #435)

Given an array of intervals, find the minimum number of intervals you need to remove to make the rest non-overlapping.

Solution:

def eraseOverlapIntervals(intervals):
    if not intervals:
        return 0
    
    intervals.sort(key=lambda x: x[1])
    count = 0
    end = intervals[0][1]
    
    for i in range(1, len(intervals)):
        if intervals[i][0] < end:
            count += 1
        else:
            end = intervals[i][1]
    
    return count

Explanation: Sort by end time. Greedily keep intervals with earliest end times. When we encounter an overlapping interval, we remove it (count++). This maximizes the number of non-overlapping intervals we can keep.

Time Complexity: O(n log n)

Space Complexity: O(1)

Problem 4: Gas Station (LeetCode #134)

There are n gas stations along a circular route. Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Solution:

def canCompleteCircuit(gas, cost):
    total_tank = 0
    current_tank = 0
    start = 0
    
    for i in range(len(gas)):
        total_tank += gas[i] - cost[i]
        current_tank += gas[i] - cost[i]
        
        if current_tank < 0:
            start = i + 1
            current_tank = 0
    
    return start if total_tank >= 0 else -1

Explanation: We track total_tank (sum of all gas - cost) and current_tank. If current_tank becomes negative, we can't start from previous positions, so we start from next position. If total_tank >= 0, there's a solution starting at 'start'.

Time Complexity: O(n)

Space Complexity: O(1)

Problem 5: Partition Labels (LeetCode #763)

A string S of lowercase English letters is given. Partition this string into as many parts as possible so that each letter appears in at most one part.

Solution:

def partitionLabels(s):
    last_occurrence = {char: i for i, char in enumerate(s)}
    
    result = []
    start = 0
    end = 0
    
    for i, char in enumerate(s):
        end = max(end, last_occurrence[char])
        if i == end:
            result.append(end - start + 1)
            start = i + 1
    
    return result

Explanation: First, record the last occurrence of each character. Then, greedily extend the partition until we reach the last occurrence of all characters in current partition. When i == end, we've completed a partition.

Time Complexity: O(n)

Space Complexity: O(1) - at most 26 characters