Advanced Greedy Techniques: Priority Queues, Two-Pass Greedy, and Lookahead Strategies

Basic greedy gets you through Easy and Medium problems. But Hard-level greedy requires advanced techniques that most developers never learn.

This guide teaches you four advanced greedy patterns that unlock the hardest problems: two-pass greedy, greedy with priority queues, lookahead strategies, and greedy with preprocessing.

TL;DR

Four advanced techniques:

1. Two-Pass Greedy - Handle constraints from both directions (Candy)
2. Greedy + Priority Queue - Dynamic selection of optimal element
3. Greedy + Lookahead - BFS-style range expansion (Jump Game II)
4. Greedy + Preprocessing - Monotonic stack + greedy (Remove K Digits)

When basic greedy isn't enough:

• Multiple conflicting constraints
• Need dynamic optimal selection
• Require lookahead
• Complex state management

When Basic Greedy Isn't Enough

Limitations of Basic Greedy

Basic greedy works when:

• Single pass suffices
• Constraints from one direction
• Static selection criteria

Basic greedy fails when:

• ❌ Constraints from multiple directions
• ❌ Need to track dynamic optimal
• ❌ Require lookahead
• ❌ Complex dependencies

Recognizing Advanced Patterns

Two-pass needed when:

• "Each element must satisfy left AND right constraints"
• Example: Candy (#135)

Priority queue needed when:

• "Select k best elements dynamically"
• "Maintain optimal while adding/removing"
• Example: Hire K Workers (#857)

Lookahead needed when:

• "Minimum steps/jumps"
• "Expand reachable range"
• Example: Jump Game II (#45)

Technique 1: Two-Pass Greedy

The Pattern

Problem type: Each element has constraints from both left and right neighbors.

Solution: Two passes—left-to-right, then right-to-left—combining results.

Why it works: Each pass handles one direction's constraints. Combining ensures both are satisfied.

Problem: Candy (LeetCode #135)

Problem: Distribute candies such that:

1. Each child gets at least 1 candy
2. Children with higher rating get more than neighbors

Why one pass fails:

Ratings: [1, 2, 3, 2, 1]

Left-to-right only:
  candies: [1, 2, 3, 1, 1]
  Child 3 (rating=2) has 1 candy
  But child 4 (rating=1) also has 1 candy
  Violates: higher rating should get more ✗

Two-pass solution:

def candy(ratings: List[int]) -> int:
    """
    Two-pass greedy for Candy problem.
    Time: O(n), Space: O(n)
    """
    n = len(ratings)
    candies = [1] * n
    
    # Pass 1: Left to right
    # Ensure right neighbor gets more if rated higher
    for i in range(1, n):
        if ratings[i] > ratings[i-1]:
            candies[i] = candies[i-1] + 1
    
    # Pass 2: Right to left
    # Ensure left neighbor gets more if rated higher
    for i in range(n-2, -1, -1):
        if ratings[i] > ratings[i+1]:
            candies[i] = max(candies[i], candies[i+1] + 1)
    
    return sum(candies)

# Example
print(candy([1,2,3,2,1]))  # 9
# candies: [1,2,3,2,1]

Why it works:

• Pass 1 ensures: if ratings[i] > ratings[i-1], then candies[i] > candies[i-1]
• Pass 2 ensures: if ratings[i] > ratings[i+1], then candies[i] > candies[i+1]
• Taking max in pass 2 preserves pass 1 constraints
• Both constraints satisfied ✓

Template: Two-Pass Greedy

def two_pass_greedy(arr):
    n = len(arr)
    result = [initial_value] * n
    
    # Pass 1: Left to right
    for i in range(1, n):
        if left_constraint(arr, i):
            result[i] = update_based_on_left(result, i)
    
    # Pass 2: Right to left
    for i in range(n-2, -1, -1):
        if right_constraint(arr, i):
            result[i] = combine(result[i], 
                               update_based_on_right(result, i))
    
    return aggregate(result)

Technique 2: Greedy with Priority Queue

The Pattern

Problem type: Need to dynamically select optimal element while adding/removing items.

Solution: Use heap to maintain optimal element, greedy selection based on heap top.

Why it works: Heap gives O(log n) access to optimal, enabling greedy decisions.

Problem: Minimum Cost to Hire K Workers (LeetCode #857)

Problem: Hire exactly k workers, minimize cost while maintaining wage/quality ratio.

Greedy insight: Sort by ratio, use max heap to track k workers with minimum total quality.

Solution:

import heapq

def mincostToHireWorkers(quality, wage, k):
    """
    Greedy with priority queue.
    Time: O(n log n), Space: O(n)
    """
    # Create (ratio, quality, wage) tuples
    workers = sorted([(w/q, q, w) for q, w in zip(quality, wage)])
    
    heap = []  # Max heap (negate for max)
    sum_quality = 0
    min_cost = float('inf')
    
    for ratio, q, w in workers:
        # Add current worker
        heapq.heappush(heap, -q)  # Max heap
        sum_quality += q
        
        # If more than k workers, remove highest quality
        if len(heap) > k:
            sum_quality += heapq.heappop(heap)  # Removes -max
        
        # If exactly k workers, calculate cost
        if len(heap) == k:
            min_cost = min(min_cost, sum_quality * ratio)
    
    return min_cost

Why it works:

• Sort by ratio ensures we consider ratios in increasing order
• For each ratio, we want minimum total quality among k workers
• Max heap lets us remove highest quality worker when needed
• Greedy: for each ratio, minimize quality sum ✓

Template: Greedy + Priority Queue

import heapq

def greedy_with_heap(items, k):
    # Sort by greedy criterion
    items.sort(key=lambda x: x.criterion)
    
    heap = []
    state = initial_state
    result = initial_result
    
    for item in items:
        # Add to heap
        heapq.heappush(heap, item.value)
        state = update_state(state, item)
        
        # Maintain size k
        if len(heap) > k:
            removed = heapq.heappop(heap)
            state = update_state_after_removal(state, removed)
        
        # Update result when condition met
        if len(heap) == k:
            result = update_result(result, state, item)
    
    return result

Technique 3: Greedy with Lookahead

The Pattern

Problem type: Find minimum steps/jumps by expanding reachable range.

Solution: BFS-style greedy—track current range and farthest reach, increment steps when leaving range.

Why it works: Think of it as BFS levels. Each "level" is a jump, expand to farthest reachable.

Problem: Jump Game II (LeetCode #45)

Problem: Find minimum jumps to reach end.

Greedy insight: Track current jump's range and farthest reach. Increment jumps when leaving current range.

Solution:

def jump(nums: List[int]) -> int:
    """
    Greedy with lookahead (BFS-style).
    Time: O(n), Space: O(1)
    """
    jumps = 0
    current_end = 0  # End of current jump range
    farthest = 0     # Farthest reachable
    
    for i in range(len(nums) - 1):
        # Update farthest reachable
        farthest = max(farthest, i + nums[i])
        
        # Reached end of current jump range
        if i == current_end:
            jumps += 1
            current_end = farthest
    
    return jumps

Why it works:

• Think of BFS levels: level 0 = start, level 1 = reachable in 1 jump, etc.
• current_end = end of current level
• farthest = farthest position in next level
• When we reach end of current level, move to next level (increment jumps)

Visualization:

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

Level 0: [0]
  From 0, can reach: 1, 2
  current_end = 0, farthest = 2

Level 1: [1, 2]
  From 1, can reach: 2, 3, 4
  From 2, can reach: 3
  current_end = 2, farthest = 4

Reached end in 2 jumps ✓

Technique 4: Greedy with Preprocessing

The Pattern

Problem type: Need to maintain monotonic property while making greedy choices.

Solution: Use monotonic stack for preprocessing, then greedy selection.

Why it works: Monotonic stack maintains optimal candidates, greedy picks from them.

Problem: Remove K Digits (LeetCode #402)

Problem: Remove k digits to get smallest number.

Greedy insight: Use monotonic increasing stack. Remove larger digits when possible.

Solution:

def removeKdigits(num: str, k: int) -> str:
    """
    Greedy with monotonic stack.
    Time: O(n), Space: O(n)
    """
    stack = []
    
    for digit in num:
        # Remove larger digits while we can
        while stack and k > 0 and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    
    # Remove remaining k digits from end
    stack = stack[:-k] if k > 0 else stack
    
    # Remove leading zeros
    result = ''.join(stack).lstrip('0')
    
    return result if result else '0'

# Example
print(removeKdigits("1432219", 3))  # "1219"
# Remove 4, 3, 2 → "1219"

Why it works:

• Monotonic stack ensures we keep smallest digits in order
• Greedy: remove larger digit when we see smaller one
• Maintains lexicographic order ✓

Complexity Analysis

Practice Problems

Two-Pass:

1. Candy (#135)
2. Trapping Rain Water (#42) - can use two-pass

Priority Queue:
3. Minimum Cost to Hire K Workers (#857)
4. Meeting Rooms II (#253)
5. IPO (#502)

Lookahead:
6. Jump Game II (#45)
7. Jump Game III (#1306)

Preprocessing:
8. Remove K Digits (#402)
9. Create Maximum Number (#321)

Conclusion

Advanced greedy techniques unlock Hard-level problems.

Four techniques:

1. Two-pass - bidirectional constraints
2. Priority queue - dynamic selection
3. Lookahead - BFS-style expansion
4. Preprocessing - monotonic stack

Master these, and you'll solve advanced greedy problems with confidence. For more patterns, see the complete greedy guide, Greedy Proof Techniques, and Candy: Two-Pass Greedy.