Greedy Algorithms and Dynamic Programming: Proof Strategies and Implementation Patterns

This document explores systematic approaches to proving greedy algorithm correctness and implementing dynamic programming solutions, covering essential proof patterns and practical implementation strategies used in top-tier technical interviews.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Are we guaranteed that the input array is sorted or can it be unsorted?
2. Can we modify the input array in-place, or do we need to preserve the original?
3. What is the expected time complexity target for the follow-up? O(n) or O(n log n)?
4. Are there any constraints on the size of the input (e.g., up to 10^5 elements)?
5. Should we return indices or values, and how should we handle duplicate elements?

Restate the pattern or problem type in your own words: This pattern involves selecting optimal elements from a collection to maximize or minimize some objective function, where local greedy choices lead to globally optimal solutions. The key insight is that we can make a locally optimal choice at each step without needing to reconsider previous decisions.

Clarify the signal words and constraint shape that point to it:

• Signal words: "maximize", "minimize", "best", "optimal", "greedy choice"
• Constraint shape: Problems with optimal substructure and greedy choice property, where local optimization decisions don't affect future choices
• Common phrasing: "find the maximum number of non-overlapping intervals", "maximize profit with constraints", or "select items to maximize value under capacity"

Note any assumptions you are making:

• The problem exhibits optimal substructure (optimal solution contains optimal solutions to subproblems)
• The greedy choice property holds (a locally optimal choice leads to a globally optimal solution)
• Input data can be processed in a specific order (often requires sorting or preprocessing)

Identify whether the pattern is best suited for static, streaming, or online scenarios: This pattern is primarily suited for static scenarios where all input data is available upfront, as greedy algorithms typically require global knowledge to make optimal choices. It's less appropriate for streaming or online scenarios where decisions must be made without future information, though some variants can work with limited lookahead.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Maximum" or "minimum" optimization objectives
• Problems asking for the "best" solution according to some criteria
• "Most" or "least" variants of counting or arrangement problems
• Problems where local optimal choices lead to global optimum
• "Greedy" or "optimal" phrasing in the problem description

Why this pattern fits better than the most common alternatives:

• Unlike dynamic programming, greedy approaches often have O(n) time complexity instead of O(n²) or higher
• They're more intuitive and easier to implement than complex DP state transitions
• When the greedy choice property holds, there's no need for expensive memoization or tabulation
• Greedy algorithms typically use O(1) space vs O(n) for DP solutions

Conditions where a variation or related pattern applies instead:

• When subproblems overlap and require memoization (classic DP)
• When optimal solution depends on future states (backtracking or DP with state dependencies)
• When there are multiple constraints that must be satisfied simultaneously (constraint satisfaction problems)
• When the optimal substructure property doesn't hold for greedy selection

The core insight that makes this pattern work: The key insight is that in certain optimization problems, making the locally optimal choice at each step leads to a globally optimal solution. This requires proving that the greedy choice property and optimal substructure exist for the specific problem instance.

This pattern is particularly effective when:

1. The problem exhibits the greedy choice property: a locally optimal move leads to a globally optimal solution
2. The problem has optimal substructure: an optimal solution contains optimal solutions to subproblems
3. There's a clear ordering or ranking of choices that can be processed sequentially

3. Approach Evolution

Interview communication script:

My first instinct is to think about this as a classic greedy problem because we're trying to make locally optimal choices at each step. But that approach might not work for all cases, so let me think about whether we can prove optimality or if we need dynamic programming.

If I just greedily pick the maximum element at each step, that's O(n²) because for each selection I have to scan the remaining array to find the maximum. But that's inefficient.

Let me think about how to optimize this... I notice that if I maintain a sorted structure or use a priority queue, I can reduce the maximum finding to O(log n) per operation. Actually, let me reconsider if this is really a greedy problem or if there's a better way to think about it.

Wait, I'm overcomplicating this. Looking more carefully at the problem structure, I think we're looking for a greedy approach that can be optimized with data structures. The key insight is that we want to make decisions that lead to global optimality, and we can maintain some invariant to make this efficient.

Let me think about what makes a greedy approach work here. We're looking for a sequence of decisions where each choice is locally optimal and leads to a globally optimal solution.

Brute-force approach and why it is not ideal:

The brute force approach would be to try all possible ways to select elements and find the one that maximizes our objective function. For example, if we're selecting k elements from an array to maximize their sum, we could generate all combinations of size k and pick the one with maximum sum.

This approach has time complexity O(C(n,k)) which is exponential in the worst case, making it completely impractical for large inputs. Even with small k, we're looking at O(n^k) complexity which is still too slow.

Improved approach and the key optimization:

The improved approach uses a greedy strategy with data structure optimization. Instead of generating all combinations, we can use a max-heap or priority queue to efficiently find and remove the maximum elements.

For instance, if we're selecting k elements to maximize sum:

1. Build a max-heap from all elements - O(n) time
2. Extract the maximum k times - O(k log n) total time

The key optimization is maintaining the heap property so we don't have to re-sort or scan the entire array each time. This reduces our complexity from O(n²) to O(n + k log n).

Final approach with step-by-step reasoning:

The final approach uses greedy selection with a priority queue (max-heap) to efficiently find the optimal elements.

First, I'll analyze what makes a greedy solution valid for this problem:

1. We can make locally optimal choices at each step
2. These local choices lead to a globally optimal solution (provable by exchange argument)
3. We can efficiently maintain the state needed to make these choices

The algorithm works as follows:

1. Build a max-heap from input elements - O(n)
2. Extract the maximum element k times - O(k log n)
3. Return the selected elements in order

Important invariants that must hold:

• The heap always contains all remaining eligible elements
• At each step, we select the element that contributes most to our objective function
• The selection process maintains the property that no better solution exists

Alternative approach considerations:

While greedy is optimal for this specific structure, there are cases where DP might be needed:

• When we have overlapping subproblems that can't be solved greedily
• When the optimal solution requires considering multiple constraints simultaneously
• When we need to track which specific elements were selected rather than just their values

The greedy approach works here because we're making independent decisions that don't affect future choices, and the objective function has a monotonic property that allows local optimization to lead to global optimum.

The key insight is that we're not just looking for any maximum, but rather the optimal sequence of selections that maximizes our target function. This is where the greedy property applies - each selection is optimal for the remaining problem size.

For problems that don't have this greedy property, we'd need to use dynamic programming or backtracking approaches instead.

4. Data Structure Choice

For the greedy and dynamic programming approach to solving optimization problems, the primary data structures chosen are:

1. Arrays/Lists for State Representation

• Used to store intermediate results or current state during DP transitions
• Time complexity: O(1) for access and updates
• Space complexity: O(n) where n is the problem size

2. Priority Queues (Heaps)

• Essential for greedy algorithms that require maintaining minimum/maximum elements efficiently
• Time complexity: O(log n) for insertions and deletions
• Space complexity: O(n) for storing elements

3. Hash Maps/Tables

• Used to memoize DP states or cache greedy decisions for reuse
• Time complexity: O(1) average for lookups and updates
• Space complexity: O(n) for storing computed states

4. Stacks/Queues

• Used in greedy algorithms that process elements in specific orders (e.g., monotonic stacks for problems like largest rectangle in histogram)
• Time complexity: O(1) for push/pop operations
• Space complexity: O(n)

The key insight is that the choice depends on what information needs to be tracked and accessed efficiently. For greedy problems, we typically need fast access to optimal choices at each step, while DP solutions require storage of computed subproblems. The combination of these structures allows us to achieve optimal time complexity while maintaining clean, readable code.

The helper structure used is often a simple state tracking object that encapsulates the relevant parameters for each subproblem or greedy choice, making the code more maintainable and reducing parameter passing complexity.

5. Algorithm Walkthrough

Let me trace through the algorithm using the example nums = [1, 2, 3, 4, 5] with target k = 10.

Step 1: Initialize variables

• left = 0, right = 0
• currentSum = 0
• minLength = Integer.MAX_VALUE

Step 2: Expand window by moving right pointer

• right = 0: currentSum = 1, window = [1]
• right = 1: currentSum = 3, window = [1,2]
• right = 2: currentSum = 6, window = [1,2,3]
• right = 3: currentSum = 10, window = [1,2,3,4]

Step 3: Found valid window [1,2,3,4] with sum = 10

• currentSum >= k is true
• minLength = Math.min(Integer.MAX_VALUE, 4) = 4
• Contract window by moving left pointer

Step 4: Contract window

• left = 1: currentSum = 9, window = [2,3,4]
• left = 2: currentSum = 7, window = [3,4]
• left = 3: currentSum = 4, window = [4]

Step 5: Continue expanding

• right = 4: currentSum = 9, window = [4,5]
• right = 5: End of array, no more expansion possible

Step 6: Final result

• minLength = 4 (window [1,2,3,4])
• Return 4

The algorithm maintains the key invariant that currentSum represents the sum of elements in the current sliding window. When we find a valid window, we immediately update the minimum length and continue contracting to explore other potential windows.

Edge cases handled:

• Empty array returns 0
• Single element arrays with sum ≥ k return 1
• Arrays where no valid subarray exists return 0

6. Java Solution

import java.util.*;

public class GreedyAndDP {
    
    /**
     * Problem: Activity Selection - Given start and end times of activities,
     * select maximum number of non-overlapping activities.
     * 
     * Approach: Greedy - Sort by end time and pick earliest ending non-overlapping.
     */
    public static int activitySelection(int[] start, int[] end) {
        if (start == null || end == null || start.length == 0) {
            return 0;
        }
        
        // Create list of activities with start and end times
        List<Activity> activities = new ArrayList<>();
        for (int i = 0; i < start.length; i++) {
            activities.add(new Activity(start[i], end[i]));
        }
        
        // Sort by end time - greedy choice
        Collections.sort(activities, Comparator.comparingInt(a -> a.end));
        
        int count = 0;
        int lastEnd = -1;
        
        for (Activity activity : activities) {
            // If current activity starts after last selected ends, select it
            if (activity.start >= lastEnd) {
                count++;
                lastEnd = activity.end;
            }
        }
        
        return count;
    }
    
    /**
     * Problem: Coin Change - Find minimum coins to make amount.
     * 
     * Approach: Dynamic Programming - Build up from smaller subproblems.
     */
    public static int coinChange(int[] coins, int amount) {
        if (amount < 0 || coins == null || coins.length == 0) {
            return -1;
        }
        
        // dp[i] = minimum coins needed to make amount i
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0; // Base case: 0 coins for amount 0
        
        // For each amount from 1 to target
        for (int i = 1; i <= amount; i++) {
            // Try each coin denomination
            for (int coin : coins) {
                if (coin <= i && dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
    
    /**
     * Problem: Maximum Subarray Sum (Kadane's Algorithm)
     * 
     * Approach: Greedy - At each position, decide whether to extend or start fresh.
     */
    public static int maxSubarraySum(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int maxSum = nums[0];
        int currentSum = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            // Either extend existing subarray or start new one
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return maxSum;
    }
    
    /**
     * Problem: Job Scheduling - Max profit with job dependencies.
     * 
     * Approach: Dynamic Programming with sorting and binary search.
     */
    public static int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        if (startTime == null || endTime == null || profit == null) {
            return 0;
        }
        
        int n = startTime.length;
        Job[] jobs = new Job[n];
        for (int i = 0; i < n; i++) {
            jobs[i] = new Job(startTime[i], endTime[i], profit[i]);
        }
        
        // Sort jobs by end time
        Arrays.sort(jobs, Comparator.comparingInt(j -> j.end));
        
        // dp[i] = max profit using jobs 0 to i
        int[] dp = new int[n];
        dp[0] = jobs[0].profit;
        
        for (int i = 1; i < n; i++) {
            // Option 1: Don't take current job
            int profitWithout = dp[i - 1];
            
            // Option 2: Take current job + best profit before compatible jobs
            int profitWith = jobs[i].profit;
            int lastCompatible = findLastCompatible(jobs, i);
            
            if (lastCompatible != -1) {
                profitWith += dp[lastCompatible];
            }
            
            dp[i] = Math.max(profitWithout, profitWith);
        }
        
        return dp[n - 1];
    }
    
    private static int findLastCompatible(Job[] jobs, int currentIndex) {
        // Binary search for latest job that ends before current job starts
        int left = 0, right = currentIndex - 1;
        int result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (jobs[mid].end <= jobs[currentIndex].start) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
    // Helper class for activity selection
    static class Activity {
        int start, end;
        Activity(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
    
    // Helper class for job scheduling
    static class Job {
        int start, end, profit;
        Job(int start, int end, int profit) {
            this.start = start;
            this.end = end;
            this.profit = profit;
        }
    }
}

7. Complexity Analysis

Time Complexity: O(n log n)

The dominant cost comes from sorting the intervals, which takes O(n log n) time. The subsequent iteration through the sorted intervals is O(n), making the overall time complexity O(n log n). This is optimal for this problem since we must examine each interval at least once and sorting is necessary to process them in order.

Space Complexity: O(1)

We only use a constant amount of extra space for variables like lastEnd, count, and loop indices. The sorting operation typically uses O(log n) space for the recursion stack in Java's Arrays.sort(), but this is considered part of the input processing overhead rather than auxiliary space.

Why These Bounds Are Correct

The O(n log n) time bound is tight because:

1. We must sort to process intervals by their end times
2. Any algorithm that solves this problem must examine all n intervals
3. The sorting step is unavoidable for the greedy approach to work

The O(1) space bound holds because:

1. We don't create any data structures that scale with input size
2. The sorting is done in-place on the original array
3. Only a fixed number of variables are used for tracking

Optimality

This solution is optimal in both time and space complexity. Any correct algorithm for this problem must sort the intervals or equivalent work, making O(n log n) time unavoidable. The space complexity is optimal since we only need to track a constant number of state variables regardless of input size.

The solution achieves the best possible trade-off between time and space for this specific variant of interval scheduling, where we want to maximize the number of non-overlapping intervals.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: The solution should handle empty input gracefully, typically returning 0 or null for optimal results
• Single element: A single item array should work correctly, with no operations needed
• Two elements: Must verify that the greedy choice still applies when only two items exist

Duplicate Values and Repeated States

• Identical elements: Arrays with all identical values can break greedy assumptions if the problem requires unique selections
• Overlapping intervals: When intervals have same start/end times, the greedy selection may be ambiguous
• Ties in optimization criteria: When multiple items have same "best" score, the choice between them can affect final result

Boundary Conditions

• Array bounds: Ensure proper index checking to avoid ArrayIndexOutOfBoundsException
• Zero values: Items with zero weight/cost may be selected when they shouldn't be in some contexts
• Negative numbers: If weights/costs can be negative, greedy may no longer work (e.g., negative weight intervals in scheduling)

Common Implementation Mistakes

• Incorrect sorting criteria: Sorting by wrong field (e.g., weight instead of ratio) leads to wrong greedy choices
• Not maintaining invariants: Failing to ensure that the greedy property holds at each step
• Improper state tracking: Not properly updating selection state after making greedy choices
• Off-by-one errors: Mismanaging loop bounds or selection indices, especially in interval problems
• Assuming greedy works without proof: Using greedy approach without verifying that local optimum leads to global optimum

Example of Common Pitfall

// Wrong: Assuming greedy works for all interval problems
// This fails when intervals can overlap in complex ways
if (intervals[i].start < intervals[i-1].end) {
    // This doesn't account for optimal non-greedy selection
}

The key is to always verify that the greedy choice property holds for your specific problem variant.

9. Alternative Approaches

There are several alternative approaches to solving problems that might be solved with greedy or dynamic programming strategies, each with distinct trade-offs:

Brute Force with Exhaustive Search: For problems like the Activity Selection Problem or Interval Scheduling, we could generate all possible subsets of activities and check which ones are valid, then pick the one with maximum count. This approach has O(2^n) time complexity and is only viable for very small inputs.

Dynamic Programming with Memoization: Instead of bottom-up DP, we could use top-down recursive approach with memoization. While this maintains the same O(n²) time complexity for Activity Selection, it introduces O(n) space overhead from the recursion stack and memoization table.

Sorting-Based Heuristics: For some greedy problems, we might sort by different criteria (e.g., sorting by start time instead of end time for Activity Selection). This would not work for the optimal greedy solution but might give approximate results with O(n log n) complexity.

Backtracking with Pruning: For optimization problems like the Knapsack problem, we could use backtracking to explore all combinations but prune branches early when we know they can't lead to better solutions than our current best.

Linear Programming: Complex optimization problems could theoretically be solved using linear programming techniques, though this would require more sophisticated mathematical tools and is typically overkill for problems that have clean greedy or DP solutions.

The chosen greedy approach is preferred because it's more intuitive, has better constants, and provides optimal solutions for problems with the greedy-choice property. These alternatives are generally less efficient or more complex to implement correctly, though they might be useful in specific constrained environments where mathematical programming tools are available.

10. Test Cases

public class TestCases {
    public static void main(String[] args) {
        // Test Case 1: Basic example from problem description
        int[] nums1 = {1, 2, 3, 4};
        // Expected: true (can form valid triangle)
        
        // Test Case 2: Invalid triangle
        int[] nums2 = {1, 2, 3};
        // Expected: false (1+2=3, not > 3)
        
        // Test Case 3: All same values
        int[] nums3 = {2, 2, 2};
        // Expected: true (2+2>2)
        
        // Test Case 4: Empty array
        int[] nums4 = {};
        // Expected: false
        
        // Test Case 5: Single element
        int[] nums5 = {1};
        // Expected: false
        
        // Test Case 6: Two elements
        int[] nums6 = {1, 2};
        // Expected: false
        
        // Test Case 7: Large numbers
        int[] nums7 = {100, 200, 300};
        // Expected: true (100+200>300)
        
        // Test Case 8: Negative numbers (if allowed)
        int[] nums8 = {-1, -2, -3};
        // Expected: false (negative sides not valid for triangle)
        
        // Test Case 9: Mixed positive/negative
        int[] nums9 = {1, -2, 3};
        // Expected: false (negative side not valid)
        
        // Test Case 10: Large valid triangle
        int[] nums10 = {5, 10, 15};
        // Expected: false (5+10=15, not > 15)
    }
}

Representative Sample Cases:

1. Valid triangle: [1, 2, 3] → false (edge case - requires strict inequality)
2. Invalid triangle: [1, 2, 3] → false (sum equals third side)
3. Valid triangle: [2, 3, 4] → true (valid triangle inequality)

Tricky Case:

• Edge case with boundary condition: [1, 2, 3] where 1+2=3 (not strictly greater)

Boundary Case:

• Minimal input: Empty array [] or single element [1] → false

These test cases cover the essential scenarios including edge conditions, invalid inputs, and boundary behaviors that help validate correctness of the triangle formation logic.

11. Final Summary

The core idea is to apply greedy selection principles with dynamic programming state tracking to optimally schedule tasks with deadlines and profits, where the goal is to maximize total profit while respecting time constraints. This solution works by first sorting tasks by their deadlines and then using a greedy approach to select the most profitable tasks that can fit within the available time window, maintaining a priority queue of selected tasks to efficiently manage the selection process. The efficiency comes from avoiding redundant computations through dynamic programming state tracking and leveraging the greedy property that local optimal choices lead to global optimum solutions.