Binary Search on Answer Space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173

from typing import List
 
def shipWithinDays(weights: List[int], days: int) -> int:
    """
    LeetCode 1011: Capacity To Ship Packages Within D Days
    
    Find the minimum ship capacity to ship all packages within 'days' days.
    Packages must be shipped in order (contiguous groups).
    
    Approach: Binary search on answer space (minimax pattern)
    - Answer space: [max(weights), sum(weights)]
    - Feasibility: can we ship with given capacity in ≤ days?
    
    Time Complexity: O(n * log(sum - max)) where n = len(weights)
    Space Complexity: O(1) extra space
    
    Args:
        weights: List of package weights (must ship in this order)
        days: Maximum number of days allowed
        
    Returns:
        Minimum ship capacity needed
    """
    
    def can_ship_in_days(capacity: int) -> bool:
        """
        Feasibility predicate: Can we ship all packages in ≤ 'days' days
        with the given ship capacity?
        
        Strategy: Greedy loading
        - Each day, load packages consecutively until capacity is reached
        - Start a new day when adding next package would exceed capacity
        - Count days needed; return True if ≤ allowed days
        
        Time: O(n) - single pass through packages
        """
        days_needed = 1      # Start with day 1
        current_load = 0     # Weight loaded today
        
        for weight in weights:
            # Can we fit this package in today's ship?
            if current_load + weight <= capacity:
                current_load += weight
            else:
                # Start a new day
                days_needed += 1
                current_load = weight
                
                # Early termination: already exceeded allowed days
                if days_needed > days:
                    return False
        
        return days_needed <= days
    
    # ==========================================
    # STEP 1: Define the search space bounds
    # ==========================================
    
    # Lower bound: Must fit the heaviest single package
    # If max(weights) = 10, ship capacity must be at least 10
    lo = max(weights)
    
    # Upper bound: Ship everything in one day
    # If sum(weights) = 55, capacity 55 definitely works (worst case)
    hi = sum(weights)
    
    # ==========================================
    # STEP 2: Binary search for minimum capacity
    # ==========================================
    
    # Minimax pattern: find smallest feasible capacity
    answer = hi  # Default to upper bound (always feasible)
    
    while lo <= hi:
        mid = lo + (hi - lo) // 2  # Avoid integer overflow
        
        if can_ship_in_days(mid):
            # This capacity works! Record and try smaller
            answer = mid
            hi = mid - 1  # SEARCH LEFT: looking for minimum
        else:
            # Too small; need larger capacity
            lo = mid + 1
    
    return answer
 
 
# ==========================================
# TEST CASES AND VERIFICATION
# ==========================================
 
def test_ship_within_days():
    """Comprehensive test suite"""
    
    # Example 1: Standard case
    assert shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5) == 15
    
    # Example 2: Heavy single package
    assert shipWithinDays([3,3,3,3,3,100,3,3,3,3], 5) == 100
    
    # Example 3: One package per day
    assert shipWithinDays([1,2,3,4,5], 5) == 5
    
    # Edge case: Single package
    assert shipWithinDays([10], 1) == 10
    
    # Edge case: All same weight
    assert shipWithinDays([5,5,5,5,5], 3) == 10  # [5,5], [5,5], [5]
    
    # Edge case: One day (ship everything)
    assert shipWithinDays([1,2,3,4,5], 1) == 15
    
    # Edge case: Many days (one package each)
    assert shipWithinDays([1,2,3,4,5], 10) == 5  # Just need max(weights)
    
    print("All tests passed! ✓")
 
 
# Run tests
test_ship_within_days()
 
 
# ==========================================
# DETAILED TRACE
# ==========================================
def trace_ship_within_days(weights, days):
    """Trace the binary search execution step by step"""
    
    def can_ship(capacity):
        days_needed = 1
        current_load = 0
        daily_loads = []
        
        for weight in weights:
            if current_load + weight <= capacity:
                current_load += weight
            else:
                daily_loads.append(current_load)
                days_needed += 1
                current_load = weight
        daily_loads.append(current_load)  # Last day's load
        
        return days_needed <= days, days_needed, daily_loads
    
    lo, hi = max(weights), sum(weights)
    print(f"Tracing: weights={weights}, days={days}")
    print(f"Search space: [{lo}, {hi}]")
    print("-" * 60)
    
    iteration = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        feasible, days_used, loads = can_ship(mid)
        
        iteration += 1
        status = "✓ FEASIBLE" if feasible else "✗ INFEASIBLE"
        print(f"Iter {iteration}: capacity={mid}, days_used={days_used}, {status}")
        print(f"         Daily loads: {loads}")
        
        if feasible:
            print(f"         → Try smaller: hi = {mid - 1}")
            hi = mid - 1
        else:
            print(f"         → Need larger: lo = {mid + 1}")
            lo = mid + 1
        print()
    
    print(f"Answer: {hi + 1}")
    return hi + 1
 
 
# Trace example
trace_ship_within_days([1,2,3,4,5,6,7,8,9,10], 5)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175

from typing import List
 
def splitArray(nums: List[int], k: int) -> int:
    """
    LeetCode 410: Split Array Largest Sum
    
    Find the minimum possible value of the largest sum after splitting
    nums into k contiguous subarrays.
    
    Approach: Binary search on answer space (minimax pattern)
    - Answer space: [max(nums), sum(nums)]
    - Feasibility: can we split into ≤ k subarrays with each sum ≤ limit?
    
    Time Complexity: O(n * log(sum - max)) where n = len(nums)
    Space Complexity: O(1) extra space
    
    Args:
        nums: Array of integers to split
        k: Number of subarrays to create
        
    Returns:
        Minimum possible maximum subarray sum
    """
    
    def can_split_with_max_sum(max_sum: int) -> bool:
        """
        Feasibility predicate: Can we split into ≤ k subarrays
        where each subarray has sum ≤ max_sum?
        
        Strategy: Greedy partitioning
        - Extend current subarray while sum ≤ max_sum
        - Start new subarray when adding more would exceed max_sum
        - Count subarrays; return True if ≤ k
        
        Why "at most k" instead of "exactly k"?
        - If we can split into fewer subarrays, we can always split
          further to get exactly k (splitting a subarray only decreases
          the maximum, which is still ≤ max_sum)
        
        Time: O(n) - single pass through elements
        """
        subarrays_needed = 1     # Start with first subarray
        current_sum = 0          # Current subarray sum
        
        for num in nums:
            # Can we extend current subarray?
            if current_sum + num <= max_sum:
                current_sum += num
            else:
                # Start a new subarray
                subarrays_needed += 1
                current_sum = num
                
                # Early termination
                if subarrays_needed > k:
                    return False
        
        return subarrays_needed <= k
    
    # ==========================================
    # STEP 1: Define the search space bounds
    # ==========================================
    
    # Lower bound: At minimum, each subarray must hold max element
    lo = max(nums)
    
    # Upper bound: Everything in one subarray
    hi = sum(nums)
    
    # ==========================================
    # STEP 2: Binary search for minimum max_sum
    # ==========================================
    
    answer = hi
    
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        
        if can_split_with_max_sum(mid):
            # This max_sum works! Try smaller
            answer = mid
            hi = mid - 1
        else:
            # Too restrictive; allow larger sums
            lo = mid + 1
    
    return answer
 
 
# ==========================================
# ALTERNATIVE: Dynamic Programming Solution
# ==========================================
 
def splitArrayDP(nums: List[int], k: int) -> int:
    """
    Alternative DP solution for comparison.
    
    dp[i][j] = minimum largest sum when splitting nums[0:i] into j subarrays
    
    Time: O(n² * k) - much slower than binary search!
    Space: O(n * k)
    
    Note: This is shown for educational comparison. Binary search
    approach is strictly better for this problem.
    """
    n = len(nums)
    
    # Precompute prefix sums for O(1) range sum queries
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    
    def range_sum(i, j):
        """Sum of nums[i:j+1]"""
        return prefix[j + 1] - prefix[i]
    
    # dp[i][j] = min largest sum for nums[0:i] split into j parts
    INF = float('inf')
    dp = [[INF] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 0  # Empty array, 0 parts
    
    for i in range(1, n + 1):
        for j in range(1, min(i, k) + 1):
            # Try all possible positions for last split
            for m in range(j - 1, i):
                # nums[0:m] split into j-1 parts, nums[m:i] is the last part
                last_part_sum = range_sum(m, i - 1)
                dp[i][j] = min(dp[i][j], max(dp[m][j-1], last_part_sum))
    
    return dp[n][k]
 
 
# ==========================================
# TEST CASES
# ==========================================
 
def test_split_array():
    """Comprehensive test suite with both solutions"""
    
    test_cases = [
        ([7, 2, 5, 10, 8], 2, 18),
        ([1, 2, 3, 4, 5], 2, 9),
        ([1, 4, 4], 3, 4),
        ([1, 2, 3, 4, 5], 5, 5),
        ([1, 2, 3, 4, 5], 1, 15),
        ([10], 1, 10),
        ([2, 3, 1, 2, 4, 3], 5, 4),
    ]
    
    for nums, k, expected in test_cases:
        result_bs = splitArray(nums, k)
        result_dp = splitArrayDP(nums, k)
        
        assert result_bs == expected, f"BS failed: {nums}, k={k}, got {result_bs}, expected {expected}"
        assert result_dp == expected, f"DP failed: {nums}, k={k}, got {result_dp}, expected {expected}"
    
    print("All tests passed! ✓")
    
    # Complexity comparison
    import time
    large_input = list(range(1, 1001))  # [1, 2, ..., 1000]
    
    start = time.time()
    splitArray(large_input, 10)
    bs_time = time.time() - start
    
    start = time.time()
    # DP would be too slow: O(1000² * 10) = 10 million operations
    # splitArrayDP(large_input, 10)  # Uncomment to see slowness
    
    print(f"Binary search time for n=1000, k=10: {bs_time:.4f}s")
    print("Binary search is dramatically faster than DP!")
 
 
test_split_array()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

def greedy_with_proof(items: list[int], limit: int):
    """
    Greedy grouping with explanation of why it's optimal.
    
    Key insight: Greedy never 'wastes' capacity by starting a group
    too early. It always packs as much as possible into each group.
    """
    groups = []
    current_group = []
    current_sum = 0
    
    for item in items:
        if current_sum + item <= limit:
            # Item fits: extend current group
            current_group.append(item)
            current_sum += item
        else:
            # Item doesn't fit: finalize current group, start new
            if current_group:  # Save non-empty group
                groups.append((current_group.copy(), current_sum))
            current_group = [item]
            current_sum = item
    
    # Don't forget the last group
    if current_group:
        groups.append((current_group.copy(), current_sum))
    
    return groups
 
 
def demonstrate_greedy_optimality():
    """Show greedy is optimal through examples"""
    
    items = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    limit = 15
    
    groups = greedy_with_proof(items, limit)
    
    print(f"Items: {items}")
    print(f"Limit: {limit}")
    print(f"Greedy produced {len(groups)} groups:")
    
    for i, (group, total) in enumerate(groups, 1):
        slack = limit - total
        print(f"  Group {i}: {group} → sum={total}, slack={slack}")
    
    print()
    print("Why greedy is optimal:")
    print("- Each group is packed as full as possible")
    print("- Moving any item to previous group would exceed limit")
    print("- Therefore, no way to use fewer groups")
 
 
demonstrate_greedy_optimality()
 
# Output:
# Items: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# Limit: 15
# Greedy produced 5 groups:
#   Group 1: [1, 2, 3, 4, 5] → sum=15, slack=0
#   Group 2: [6, 7] → sum=13, slack=2
#   Group 3: [8] → sum=8, slack=7
#   Group 4: [9] → sum=9, slack=6
#   Group 5: [10] → sum=10, slack=5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

def comprehensive_edge_case_tests():
    """Test all edge cases to ensure robustness"""
    
    test_cases = [
        # (nums, k, expected_answer, description)
        ([42], 1, 42, "Single element"),
        ([5, 5, 5, 5], 2, 10, "All same - even split"),
        ([5, 5, 5, 5, 5], 2, 15, "All same - uneven split"),
        ([1, 2, 3], 3, 3, "k equals length"),
        ([1, 2, 3, 4, 5], 1, 15, "k equals 1"),
        ([1, 1, 100, 1, 1], 3, 100, "One huge element"),
        ([1, 1, 1, 1, 100], 2, 100, "Huge element at end"),
        ([100, 1, 1, 1, 1], 2, 100, "Huge element at start"),
        ([1], 1, 1, "Minimal input"),
        ([1, 1, 1, 1, 1], 5, 1, "All ones, each separate"),
        ([10, 10, 10], 3, 10, "Elements equal minimum non-trivial limit"),
    ]
    
    for nums, k, expected, description in test_cases:
        result = splitArray(nums, k)
        status = "✓" if result == expected else "✗"
        print(f"{status} {description}: splitArray({nums}, {k}) = {result} (expected {expected})")
        assert result == expected, f"Failed: {description}"
    
    print("\nAll edge cases passed!")
 
 
# Common bugs to avoid:
def buggy_feasibility_v1(nums, limit):
    """BUG: Forgetting to count the last group"""
    groups = 0  # Should start at 1
    current = 0
    for num in nums:
        if current + num <= limit:
            current += num
        else:
            groups += 1
            current = num
    return groups  # BUG: missed adding 1 for final group!
 
 
def buggy_feasibility_v2(nums, limit):
    """BUG: Off-by-one in comparison"""
    groups = 1
    current = 0
    for num in nums:
        if current + num < limit:  # BUG: should be <=
            current += num
        else:
            groups += 1
            current = num
    return groups
 
 
def correct_feasibility(nums, limit):
    """CORRECT implementation"""
    groups = 1  # Start with 1
    current = 0
    for num in nums:
        if current + num <= limit:  # Correct: <=
            current += num
        else:
            groups += 1
            current = num
    return groups  # No +1 needed because we started at 1
 
 
# Demonstrate the bugs
nums = [1, 2, 3, 4, 5]
limit = 9
 
print(f"Buggy v1 (forgot last group): {buggy_feasibility_v1(nums, limit)}")  # Wrong!
print(f"Buggy v2 (< instead of <=): {buggy_feasibility_v2(nums, limit)}")    # Wrong!  
print(f"Correct: {correct_feasibility(nums, limit)}")                          # Correct!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

def minEatingSpeed(piles: list[int], h: int) -> int:
    """
    LeetCode 875: Koko Eating Bananas
    
    Koko loves bananas. There are n piles. She can eat at speed k bananas/hour.
    Each hour, she chooses a pile and eats k bananas (or finishes the pile).
    What's the minimum k to finish all bananas in h hours?
    
    This is essentially "Capacity to Ship" with:
    - "capacity" = eating speed k
    - "days" = hours h
    - "packages" = piles
    
    Key difference: A pile takes ceil(pile_size / k) hours to eat,
    even if pile_size < k (she doesn't move between piles within an hour).
    """
    import math
    
    def can_finish(speed: int) -> bool:
        """Can Koko finish all piles in h hours eating at given speed?"""
        hours_needed = 0
        for pile in piles:
            hours_needed += math.ceil(pile / speed)
            if hours_needed > h:
                return False
        return hours_needed <= h
    
    # Bounds
    lo = 1                # Minimum possible speed
    hi = max(piles)       # At max(piles), each pile takes 1 hour
    
    # Binary search (minimax)
    answer = hi
    while lo <= hi:
        mid = (lo + hi) // 2
        if can_finish(mid):
            answer = mid
            hi = mid - 1
        else:
            lo = mid + 1
    
    return answer
 
 
# The pattern is the same! Only the feasibility check differs.
print(minEatingSpeed([3, 6, 7, 11], 8))  # Output: 4
print(minEatingSpeed([30, 11, 23, 4, 20], 5))  # Output: 30
 
 
def cuttingRibbons(ribbons: list[int], k: int) -> int:
    """
    LeetCode 1891: Cutting Ribbons
    
    Cut ribbons to get k pieces of equal length. Maximize that length.
    A ribbon can be cut into multiple pieces or not used at all.
    
    This is a MAXIMIN problem: maximize the minimum piece length.
    """
    def can_get_k_pieces(length: int) -> bool:
        """Can we cut ribbons to get at least k pieces of given length?"""
        pieces = 0
        for ribbon in ribbons:
            pieces += ribbon // length  # How many pieces from this ribbon
        return pieces >= k
    
    # Bounds
    lo = 1
    hi = max(ribbons)  # Can't get piece longer than longest ribbon
    
    # Binary search (MAXIMIN - search right when feasible)
    answer = 0  # Default: might not be possible
    while lo <= hi:
        mid = (lo + hi) // 2
        if can_get_k_pieces(mid):
            answer = mid
            lo = mid + 1  # Maximin: try larger
        else:
            hi = mid - 1
    
    return answer
 
 
print(cuttingRibbons([9, 7, 5], 3))  # Output: 5 (cut 9→5, keep 7→5, keep 5→5)
print(cuttingRibbons([7, 5, 9], 4))  # Output: 4