DSA Fundamentals: Greedy Algorithms - From Theory to LeetCode Practice

Greedy algorithms are a powerful problem-solving paradigm that makes locally optimal choices at each step, hoping to find a global optimum. While not always applicable, greedy algorithms provide elegant and efficient solutions to many optimization problems, especially those involving sequences, intervals, and resource allocation.

This comprehensive guide combines theoretical understanding with practical problem-solving, featuring solutions to essential LeetCode problems that demonstrate core greedy algorithmic patterns.

Understanding Greedy Algorithms

Greedy Algorithm Fundamentals

Greedy algorithms make the best local choice at each decision point, without considering future consequences. The key insight is that sometimes, making locally optimal choices leads to a globally optimal solution.

When to Use Greedy Algorithms

Greedy algorithms work well when:

• Optimal substructure: Optimal solution contains optimal solutions to subproblems
• Greedy choice property: Locally optimal choice leads to globally optimal solution
• No need to reconsider: Once a choice is made, it's never reconsidered
• Problem can be solved incrementally: Build solution step by step

Common problem types:

• Maximum/minimum subarray problems
• Jump and reachability problems
• Interval scheduling
• Resource allocation
• Path finding with constraints

Greedy vs Dynamic Programming

Aspect	Greedy	Dynamic Programming
Decision making	Make best local choice	Consider all possibilities
Subproblems	Don't revisit decisions	May revisit subproblems
Time complexity	Usually O(n) or O(n log n)	Often O(n²) or exponential
Space complexity	Usually O(1)	Often O(n) or O(n²)
Proof	Requires proof of correctness	Naturally optimal
When to use	Greedy choice property holds	Overlapping subproblems

Key Greedy Patterns

1. Maximum/Minimum Subarray:

• Track running sum/max/min
• Reset when condition violated
• Update global maximum/minimum

2. Jump Problems:

• Track maximum reachable position
• Make greedy choice to jump as far as possible
• Verify reachability incrementally

3. Resource Allocation:

• Process items in optimal order
• Make greedy choices based on constraints
• Track resource usage

4. Interval Problems:

• Sort by specific criteria
• Make greedy choices about which intervals to include
• Process in order

Time Complexity Analysis

Pattern	Time Complexity	Space Complexity	Notes
Single pass greedy	O(n)	O(1)	One iteration through data
Greedy with sorting	O(n log n)	O(1)	Sorting dominates
Greedy with heap	O(n log n)	O(n)	Heap operations
Multiple passes	O(n)	O(1)	Forward and backward passes

Essential LeetCode Problems & Solutions

Let's explore fundamental greedy algorithm problems that demonstrate core decision-making patterns.

1. Maximum Subarray (LeetCode 53) - Kadane's Algorithm

Problem: Find the contiguous subarray with the largest sum.

Approach: Kadane's algorithm - track running sum, reset to 0 when sum becomes negative (greedy choice: discard negative prefix).

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        curr_sum = 0
        max_sum = float('-inf')

        for num in nums:
            # Greedy choice: reset if current sum is negative
            # Negative prefix can only reduce future sums
            if curr_sum < 0:
                curr_sum = 0

            # Add current number to running sum
            curr_sum += num

            # Update maximum sum seen so far
            max_sum = max(max_sum, curr_sum)

        return max_sum

Time Complexity: O(n) - Single pass through array

Space Complexity: O(1) - Only tracking two variables

Key Concepts:

• Greedy reset: When curr_sum < 0, reset to 0 (negative prefix hurts future sums)
• Kadane's insight: Maximum subarray ending at position i is either:
  • Extend previous subarray: curr_sum + nums[i]
  • Start new subarray: nums[i] (when previous sum is negative)
• Global maximum tracking: Keep track of maximum sum across all positions
• No need for DP table: Greedy approach eliminates need for O(n) space

Example Walkthrough:

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

i=0: num=-2, curr_sum=-2 < 0 → reset to 0, curr_sum=0, max_sum=-2
i=1: num=1, curr_sum=1, max_sum=1
i=2: num=-3, curr_sum=-2 < 0 → reset to 0, curr_sum=0, max_sum=1
i=3: num=4, curr_sum=4, max_sum=4
i=4: num=-1, curr_sum=3, max_sum=4
i=5: num=2, curr_sum=5, max_sum=5
i=6: num=1, curr_sum=6, max_sum=6
i=7: num=-5, curr_sum=1, max_sum=6
i=8: num=4, curr_sum=5, max_sum=6

Result: 6 (subarray [4, -1, 2, 1])

Why Greedy Works:

• If we have a negative prefix sum, starting fresh from current position always gives better or equal result
• We never need to consider keeping a negative prefix because it can only reduce future sums
• This local optimal choice (reset when negative) leads to global optimum

2. Jump Game (LeetCode 55)

Problem: Determine if you can reach the last index starting from index 0. Each element represents maximum jump length.

Approach 1: Backward Greedy (Target Tracking)

Start from the end and work backwards, tracking the target index we need to reach.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        target = n - 1  # Start with last index as target

        # Work backwards from second-to-last index
        for i in range(n-1, -1, -1):
            # If we can reach target from current position, update target
            if nums[i] + i >= target:
                target = i

        # If target reached index 0, we can jump from start
        return target == 0

Time Complexity: O(n) - Single backward pass

Space Complexity: O(1) - Only tracking target index

Key Concepts:

• Backward approach: Start from goal, work backwards to start
• Target update: If position i can reach current target, i becomes new target
• Greedy choice: If multiple positions can reach target, closest one is sufficient
• Final check: If target reaches index 0, path exists

Example Walkthrough:

Input: [2, 3, 1, 1, 4]

Initial: target = 4 (last index)
i=3: nums[3]=1, 3+1=4 >= 4 → target = 3
i=2: nums[2]=1, 2+1=3 >= 3 → target = 2
i=1: nums[1]=3, 1+3=4 >= 2 → target = 1
i=0: nums[0]=2, 0+2=2 >= 1 → target = 0

target == 0 → return True

Approach 2: Forward Greedy (Maximum Reach)

Track maximum reachable position while iterating forward.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        target = 0  # Maximum reachable position

        for i in range(n):
            # If current index is beyond reachable, impossible
            if i > target:
                return False

            # Update maximum reachable position
            target = max(target, nums[i] + i)

        # Check if we can reach last index
        return target >= n - 1

Time Complexity: O(n) - Single forward pass

Space Complexity: O(1) - Only tracking maximum reach

Key Concepts:

• Forward approach: Process from start to end
• Reachability check: If i > target, we can't reach position i
• Greedy update: Always update to maximum reachable position
• Early termination: Return False immediately if unreachable position found

Example Walkthrough:

Input: [2, 3, 1, 1, 4]

i=0: target=0, i=0 <= 0, target = max(0, 0+2) = 2
i=1: target=2, i=1 <= 2, target = max(2, 1+3) = 4
i=2: target=4, i=2 <= 4, target = max(4, 2+1) = 4
i=3: target=4, i=3 <= 4, target = max(4, 3+1) = 4
i=4: target=4, i=4 <= 4, target = max(4, 4+4) = 8

target=8 >= 4 → return True

Comparison:

• Backward approach: More intuitive for "can we reach goal" problems
• Forward approach: More natural for "track progress" problems
• Both are O(n) time and O(1) space
• Forward approach allows early termination

3. Gas Station (LeetCode 134)

Problem: Find starting gas station index to complete circular route. Return -1 if impossible.

Approach: Greedy - if total gas >= total cost, solution exists. Track tank level, reset starting point when tank goes negative.

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # Early termination: if total gas < total cost, impossible
        if sum(gas) < sum(cost):
            return -1

        index, tank = 0, 0

        for i in range(len(gas)):
            # Calculate net gas gain/loss at station i
            tank += (gas[i] - cost[i])

            # Greedy choice: if tank negative, can't start from any previous station
            # Reset starting point to next station
            if tank < 0:
                tank = 0
                index = i + 1

        return index

Time Complexity: O(n) - Single pass through stations

Space Complexity: O(1) - Only tracking index and tank

Key Concepts:

• Total gas check: If sum(gas) < sum(cost), impossible to complete circuit
• Net gas calculation: gas[i] - cost[i] represents net gain/loss
• Greedy reset: When tank goes negative, previous starting points won't work
• Why it works: If we can't reach station j from station i, we can't reach j from any station between i and j
• Single pass: After checking total gas, one pass finds starting point

Example Walkthrough:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]

Total check: sum(gas)=15, sum(cost)=15 → possible

i=0: tank = 0 + (1-3) = -2 < 0 → reset, index=1, tank=0
i=1: tank = 0 + (2-4) = -2 < 0 → reset, index=2, tank=0
i=2: tank = 0 + (3-5) = -2 < 0 → reset, index=3, tank=0
i=3: tank = 0 + (4-1) = 3, index=3
i=4: tank = 3 + (5-2) = 6, index=3

Return index=3

Why Greedy Reset Works:

• If we can't reach station j from station i, starting from any station between i and j also fails
• This is because we would have even less gas when reaching those intermediate stations
• Therefore, we can safely skip all previous starting points and try from j+1

4. Jump Game II (LeetCode 45)

Problem: Find minimum number of jumps to reach last index. Guaranteed that you can reach the last index.

Approach: Greedy - track current jump's end boundary and farthest reachable position. Jump when reaching current boundary.

class Solution:
    def jump(self, nums: List[int]) -> int:
        # Edge case: already at last index
        if len(nums) == 1:
            return 0

        jump, end, target = 0, 0, 0

        # Process all positions except last (don't need to jump from last)
        for i in range(len(nums) - 1):
            # Update farthest position reachable from current position
            target = max(target, nums[i] + i)

            # When we reach end of current jump's range, make a jump
            if i == end:
                jump += 1
                end = target  # Update to farthest reachable position

        return jump

Time Complexity: O(n) - Single pass through array

Space Complexity: O(1) - Only tracking jump count and boundaries

Key Concepts:

• Greedy choice: Always jump to farthest reachable position
• Jump boundaries: end represents end of current jump's range
• Target tracking: target tracks farthest position reachable with current jumps
• Jump trigger: When i == end, we've exhausted current jump's range, must jump
• Optimal substructure: Minimum jumps to position i + optimal jump from i = global optimum

Example Walkthrough:

Input: [2, 3, 1, 1, 4]

i=0: target = max(0, 0+2) = 2, i=0 == end=0 → jump=1, end=2
i=1: target = max(2, 1+3) = 4, i=1 != end=2
i=2: target = max(4, 2+1) = 4, i=2 == end=2 → jump=2, end=4
i=3: target = max(4, 3+1) = 4, i=3 != end=4
(loop ends, i < len(nums)-1)

Result: 2 jumps
Path: 0 → 1 → 4 (or 0 → 1 → 3 → 4)

Why Greedy Works:

• At each position, jumping to farthest reachable position gives maximum flexibility
• This greedy choice (maximize reach) minimizes number of jumps needed
• If we can reach position j with k jumps, we can reach any position before j with ≤ k jumps
• Therefore, greedy approach finds minimum jumps

Visualization:

nums = [2, 3, 1, 1, 4]
       0  1  2  3  4

Jump 1: Can reach positions 0-2
  - From 0: can reach up to 2
  - Choose position 1 (greedy: farthest reach from 1 is 4)

Jump 2: Can reach positions 1-4
  - From 1: can reach up to 4 (reached!)

Core Algorithm Patterns from Today's Problems

1. Kadane's Algorithm Pattern (Maximum Subarray)

When to use:

• Finding maximum/minimum sum subarray
• Problems involving contiguous sequences
• Need to track running sum with reset condition

Examples: Maximum Subarray, Maximum Product Subarray

Key characteristics:

• Track running sum/product
• Reset when condition violated (e.g., negative sum)
• Update global maximum/minimum
• O(n) time, O(1) space

Template:

def kadane_algorithm(nums):
    curr_sum = 0
    max_sum = float('-inf')

    for num in nums:
        # Greedy reset condition
        if curr_sum < 0:  # or other condition
            curr_sum = 0

        curr_sum += num
        max_sum = max(max_sum, curr_sum)

    return max_sum

2. Reachability Tracking Pattern

When to use:

• Jump problems
• Can we reach a target?
• Maximum reachable position problems

Examples: Jump Game, Jump Game II

Key characteristics:

• Track maximum reachable position
• Check if current position is reachable
• Update reach based on current position's capability
• Forward or backward iteration

Template (Forward):

def can_reach_forward(nums):
    max_reach = 0

    for i in range(len(nums)):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + nums[i])

    return max_reach >= len(nums) - 1

Template (Backward):

def can_reach_backward(nums):
    target = len(nums) - 1

    for i in range(len(nums) - 1, -1, -1):
        if i + nums[i] >= target:
            target = i

    return target == 0

3. Boundary-Based Jumping Pattern

When to use:

• Minimum jumps problems
• Problems with jump boundaries
• Need to track jump ranges

Example: Jump Game II

Key characteristics:

• Track current jump's end boundary
• Track farthest reachable position
• Jump when reaching boundary
• Greedy: always maximize reach

Template:

def min_jumps(nums):
    if len(nums) == 1:
        return 0

    jumps = 0
    end = 0  # End of current jump's range
    farthest = 0  # Farthest position reachable

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])

        if i == end:  # Reached boundary, must jump
            jumps += 1
            end = farthest

    return jumps

4. Circular Route Pattern

When to use:

• Circular/cyclic problems
• Problems with net gain/loss
• Need to find starting point

Example: Gas Station

Key characteristics:

• Check total feasibility first
• Track running sum/tank
• Reset starting point when sum goes negative
• Single pass finds solution

Template:

def circular_route(gain, cost):
    # Check total feasibility
    if sum(gain) < sum(cost):
        return -1

    start = 0
    tank = 0

    for i in range(len(gain)):
        tank += (gain[i] - cost[i])

        if tank < 0:
            tank = 0
            start = i + 1

    return start

Performance Optimization Tips

1. Early Termination

# Jump Game: return False immediately when unreachable
def canJump(nums):
    max_reach = 0
    for i in range(len(nums)):
        if i > max_reach:
            return False  # Early exit
        max_reach = max(max_reach, i + nums[i])
    return True

Key insight: Stop processing as soon as answer is determined.

2. Total Feasibility Check

# Gas Station: check total before processing
def canCompleteCircuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1  # Early exit, no solution possible

    # ... rest of logic

Key insight: Quick feasibility check can save unnecessary computation.

3. Reset Strategy in Kadane's

# Reset when negative, but consider edge case
def maxSubArray(nums):
    curr_sum = 0
    max_sum = float('-inf')  # Handle all negative numbers

    for num in nums:
        if curr_sum < 0:
            curr_sum = 0
        curr_sum += num
        max_sum = max(max_sum, curr_sum)

    return max_sum

Key insight: Initialize max_sum to negative infinity to handle edge cases.

4. Boundary Management

# Jump Game II: process up to len(nums)-1
def jump(nums):
    for i in range(len(nums) - 1):  # Don't process last index
        # ... logic

Key insight: Don't jump from last position, process only necessary indices.

Common Pitfalls and Solutions

1. Incorrect Reset Condition in Kadane's

# Wrong: Reset when sum equals 0
if curr_sum == 0:
    curr_sum = 0  # Redundant, and misses negative numbers

# Correct: Reset when sum is negative
if curr_sum < 0:
    curr_sum = 0  # Negative prefix hurts future sums

2. Off-by-One in Jump Problems

# Wrong: Check if we can reach last index incorrectly
return target >= len(nums)  # Off by one

# Correct: Last index is len(nums) - 1
return target >= len(nums) - 1

3. Missing Edge Cases

# Wrong: Assume array has at least 2 elements
def jump(nums):
    jump, end, target = 0, 0, 0
    # ... might fail for single element

# Correct: Handle edge case
def jump(nums):
    if len(nums) == 1:
        return 0
    # ... rest of logic

4. Incorrect Gas Station Logic

# Wrong: Don't check total feasibility
def canCompleteCircuit(gas, cost):
    index, tank = 0, 0
    for i in range(len(gas)):
        tank += (gas[i] - cost[i])
        if tank < 0:
            tank = 0
            index = i + 1
    return index  # Might return wrong answer if impossible

# Correct: Check total first
def canCompleteCircuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    # ... rest of logic

5. Not Updating Maximum Correctly

# Wrong: Update before checking condition
def canJump(nums):
    max_reach = 0
    for i in range(len(nums)):
        max_reach = max(max_reach, i + nums[i])  # Update first
        if i > max_reach:  # Check after update
            return False

# Correct: Check before updating
def canJump(nums):
    max_reach = 0
    for i in range(len(nums)):
        if i > max_reach:  # Check first
            return False
        max_reach = max(max_reach, i + nums[i])  # Update after

Time Complexity Comparison

Problem Complexity Summary

Problem	Brute Force	Greedy	Space	Technique
Maximum Subarray	O(n²)	O(n)	O(1)	Kadane's Algorithm
Jump Game	O(2^n)	O(n)	O(1)	Reachability Tracking
Gas Station	O(n²)	O(n)	O(1)	Circular Route
Jump Game II	O(n²)	O(n)	O(1)	Boundary Jumping

Why Greedy is Efficient

Maximum Subarray:

• Brute force: Check all subarrays → O(n²)
• Greedy: Single pass with reset → O(n)
• Savings: O(n²) → O(n)

Jump Problems:

• Brute force: Try all paths → O(2^n) or O(n²)
• Greedy: Track maximum reach → O(n)
• Savings: Exponential/polynomial → O(n)

Gas Station:

• Brute force: Try each starting point → O(n²)
• Greedy: Single pass with reset → O(n)
• Savings: O(n²) → O(n)

Conclusion

Greedy algorithms provide elegant and efficient solutions to many optimization problems by making locally optimal choices. Key takeaways:

Core Concepts Mastered:

Greedy Fundamentals:

• Local optimal choices lead to global optimum when greedy choice property holds
• No reconsideration - once a choice is made, it's final
• Optimal substructure - optimal solution contains optimal subproblem solutions
• When to use - problems with greedy choice property

Problem Types:

• Maximum subarray: Kadane's algorithm with reset strategy
• Jump problems: Reachability tracking and boundary management
• Circular routes: Total feasibility + single pass with reset
• Resource allocation: Greedy selection based on constraints

Essential Patterns Mastered Today:

Pattern 1: Kadane's Algorithm (Maximum Subarray)

Pattern 2: Reachability Tracking (Jump Game)

Pattern 3: Boundary-Based Jumping (Jump Game II)

Pattern 4: Circular Route (Gas Station)

Problem-Solving Strategies:

• Identify greedy choice property - can local optimal lead to global optimal?
• Track running state - sum, reach, tank, etc.
• Reset when beneficial - negative prefixes, unreachable positions
• Check feasibility first - total gas check, reachability validation
• Update maximums/minimums - track best value seen so far
• Handle edge cases - single element, all negative, impossible cases

Optimization Principles:

1. Make locally optimal choices - maximize/minimize at each step
2. Reset when condition violated - negative sums, unreachable positions
3. Track boundaries and limits - jump ranges, reachable positions
4. Early termination - stop when answer determined
5. Single pass when possible - O(n) solutions preferred

Greedy vs Dynamic Programming:

Use Greedy when:

• Greedy choice property holds
• Optimal substructure exists
• Can make decision without considering all possibilities
• Want O(n) or O(n log n) solution

Use DP when:

• Need to consider all possibilities
• Overlapping subproblems
• Greedy choice doesn't guarantee optimal
• Need to revisit decisions

Next Steps:

Building on greedy fundamentals, future topics will cover:

• Interval Scheduling (greedy selection criteria)
• Huffman Coding (greedy tree construction)
• Activity Selection (greedy interval problems)
• Fractional Knapsack (greedy with sorting)
• Minimum Spanning Trees (Kruskal's, Prim's algorithms)

The problems covered here represent fundamental greedy patterns that appear across technical interviews and optimization problems. Master these concepts, and you'll recognize opportunities to apply greedy thinking to transform complex problems into elegant, efficient solutions.

---

Practice Problems for Mastery:

Basic Greedy Problems:

• 53. Maximum Subarray
• 55. Jump Game
• 45. Jump Game II
• 134. Gas Station
• 121. Best Time to Buy and Sell Stock
• 122. Best Time to Buy and Sell Stock II

Intermediate Greedy Problems:

• 135. Candy
• 55. Jump Game
• 376. Wiggle Subsequence
• 392. Is Subsequence
• 406. Queue Reconstruction by Height

Advanced Greedy Problems:

• 330. Patching Array
• 435. Non-overlapping Intervals
• 452. Minimum Number of Arrows to Burst Balloons
• 621. Task Scheduler
• 763. Partition Labels

References:

• NeetCode - Algorithms
• LeetCode Patterns
• Greg Hogg DSA Algorithm YouTube Channel
• Algorithm Design Manual by Steven Skiena
• Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
• Grokking Algorithms by Aditya Bhargava

This comprehensive guide combines theoretical understanding with practical problem-solving, providing a solid foundation for mastering greedy algorithms and optimization strategies.