Split Array Largest Sum

▶

Steps

setup

Initialize prefix sums and binary search bounds

Compute prefix sums of nums to enable quick subarray sum calculations. Set low to max element (10) and high to total sum (32) as initial binary search bounds.

💡 Prefix sums let us compute any subarray sum in O(1), and setting low and high bounds defines the search space for the largest sum.

Line:

prefix = [0]
for num in nums:
    prefix.append(prefix[-1] + num)
low, high = max(nums), prefix[-1]

💡 Prefix sums and initial bounds setup the problem for binary searching the answer space.

compare

Calculate mid = (lo + hi) // 2 = 21

Calculate mid as the average of low and high, 21, to test if the array can be split into m=2 subarrays with largest sum ≤ 21.

💡 Mid is the candidate largest sum to validate; this step starts the binary search iteration.

Line:

mid = (low + high) // 2

💡 Mid divides the search space and guides the next validation step.

compare

Check if can split with max sum 21 - first subarray

Starting from prefix index 0, binary search prefix sums to find max end where subarray sum ≤ 21. Found end at index 3 (prefix[3]=14).

💡 This greedy step finds the largest subarray starting at 0 with sum ≤ mid, reducing the number of subarrays needed.

Line:

end = bisect.bisect_right(prefix, prefix[start] + max_sum, lo=start+1) - 1

💡 Binary searching prefix sums quickly finds the largest valid subarray for current mid.

compare

Check if can split with max sum 21 - second subarray

From prefix index 3, binary search prefix sums to find max end with subarray sum ≤ 21. Found end at index 4 (sum=10).

💡 Continuing greedy splits to cover the array with subarrays ≤ mid sum.

Line:

end = bisect.bisect_right(prefix, prefix[start] + max_sum, lo=start+1) - 1

💡 Second subarray sum also fits ≤ mid, so total subarrays needed is 2.

compare

Check if can split with max sum 21 - third subarray needed?

From prefix index 4, binary search prefix sums to find max end with subarray sum ≤ 21. Found end at index 5 (sum=8). Total subarrays needed: 3.

💡 More than m=2 subarrays needed means mid=21 is too small.

Line:

end = bisect.bisect_right(prefix, prefix[start] + max_sum, lo=start+1) - 1
if count > m:
    return False

💡 Mid=21 is invalid; need to search higher sums.

compare

Update low to 22 and calculate new mid = 27

Since 21 was too small, set low to 22. Calculate new mid as (22 + 32) // 2 = 27.

💡 Adjusting search space to test a larger candidate largest sum.

Line:

low = mid + 1
mid = (low + high) // 2

💡 Binary search narrows the answer space by eliminating invalid lower half.

compare

Check if can split with max sum 27 - first subarray

From prefix index 0, find max end with subarray sum ≤ 27. Found end at index 4 (sum=24).

💡 Greedy split tries to cover as much as possible under mid=27.

Line:

end = bisect.bisect_right(prefix, prefix[start] + max_sum, lo=start+1) - 1

💡 First subarray sum fits well under 27, reducing subarray count.

compare

Check if can split with max sum 27 - second subarray

From prefix index 4, find max end with subarray sum ≤ 27. Found end at index 5 (sum=8). Total subarrays needed: 2.

💡 Total subarrays needed equals m=2, so mid=27 is valid.

Line:

end = bisect.bisect_right(prefix, prefix[start] + max_sum, lo=start+1) - 1
if count > m:
    return False

💡 Mid=27 is a valid largest sum, so search space can be reduced from above.

compare

Calculate new mid = (22 + 27) // 2 = 24

Calculate mid as 24 to test if a smaller largest sum is possible.

💡 Mid moves closer to the minimal largest sum by narrowing search space.

Line:

mid = (low + high) // 2

💡 Binary search continues to narrow the answer space.

compare

Check if can split with max sum 24 - first subarray

From prefix index 0, find max end with subarray sum ≤ 24. Found end at index 4 (sum=24).

💡 Greedy split tries to maximize subarray size under mid=24.

Line:

end = bisect.bisect_right(prefix, prefix[start] + max_sum, lo=start+1) - 1

💡 First subarray sum exactly equals mid, valid split start.

compare

Check if can split with max sum 24 - second subarray

From prefix index 4, find max end with subarray sum ≤ 24. Found end at index 5 (sum=8). Total subarrays needed: 2.

💡 Total subarrays equals m=2, so mid=24 is valid.

Line:

end = bisect.bisect_right(prefix, prefix[start] + max_sum, lo=start+1) - 1
if count > m:
    return False

💡 Mid=24 is valid, so high moves down to 24.

compare

Calculate new mid = (22 + 24) // 2 = 23

Calculate mid as 23 to test if a smaller largest sum is possible.

💡 Mid moves closer to minimal largest sum by narrowing search space.

Line:

mid = (low + high) // 2

💡 Binary search continues narrowing answer space.

compare

Check if can split with max sum 23 - first subarray

From prefix index 0, find max end with subarray sum ≤ 23. Found end at index 3 (sum=14).

💡 Greedy split tries to maximize subarray size under mid=23.

Line:

end = bisect.bisect_right(prefix, prefix[start] + max_sum, lo=start+1) - 1

💡 First subarray sum fits under 23, but smaller than previous mid.

compare

Check if can split with max sum 23 - second subarray

From prefix index 3, find max end with subarray sum ≤ 23. Found end at index 4 (sum=10).

💡 Continuing greedy splits under mid=23.

Line:

end = bisect.bisect_right(prefix, prefix[start] + max_sum, lo=start+1) - 1

💡 Second subarray sum fits under 23.

compare

Check if can split with max sum 23 - third subarray needed?

From prefix index 4, find max end with subarray sum ≤ 23. Found end at index 5 (sum=8). Total subarrays needed: 3.

💡 More than m=2 subarrays needed means mid=23 is too small.

Line:

end = bisect.bisect_right(prefix, prefix[start] + max_sum, lo=start+1) - 1
if count > m:
    return False

💡 Mid=23 too small, search space moves up.

final_state

Low equals high at 24, final answer found

Low and high converge at 24, the minimal largest sum to split array into 2 subarrays.

💡 Binary search ends when low meets high, giving the answer.

Line:

return low

💡 The minimal largest sum is 24, which matches the split [7,2,5,10] and [8].

from typing import List
import bisect

def splitArray(nums: List[int], m: int) -> int:
    n = len(nums)
    prefix = [0]
    # STEP 1: Compute prefix sums
    for num in nums:
        prefix.append(prefix[-1] + num)

    def can_split(max_sum: int) -> bool:
        count = 0
        start = 0
        # STEP 3-5: Greedy split using binary search on prefix sums
        while start < n:
            end = bisect.bisect_right(prefix, prefix[start] + max_sum, lo=start+1) - 1
            count += 1
            start = end
            if count > m:
                return False
        return True

    low, high = max(nums), prefix[-1]  # STEP 1
    while low < high:
        mid = (low + high) // 2  # STEP 2,6,9,12,15
        if can_split(mid):  # STEP 8,11
            high = mid
        else:
            low = mid + 1
    return low  # STEP 16

if __name__ == '__main__':
    print(splitArray([7,2,5,10,8], 2))  # Expected output: 24

📊

Split Array Largest Sum - Watch the Algorithm Execute, Step by Step

Watching this step-by-step reveals how binary search can be applied not just on array indices but on possible answer values, and how greedy subarray splitting validates each candidate mid.

0

0

7

1

9

2

14

3

24

4

32

5

Next: lo=10 hi=32

Target: 21

0

0

7

1

9

2

14

3

24

4

32

5

Next: lo=10 hi=32

Target: 21

0

0

7

1

9

2

14

3

24

4

32

5

Next: lo=10 hi=32

Target: 21

0

0

7

1

9

2

14

3

24

4

32

5

Next: lo=10 hi=32

Target: 21

0

0

7

1

9

2

14

3

24

4

32

5

Next: lo=22 hi=32

Target: 27

0

0

7

1

9

2

14

3

24

4

32

5

Next: lo=22 hi=32

Target: 27

0

0

7

1

9

2

14

3

24

4

32

5

Next: lo=22 hi=32

Target: 27

0

0

7

1

9

2

14

3

24

4

32

5

Next: lo=22 hi=27

Target: 24

0

0

7

1

9

2

14

3

24

4

32

5

Next: lo=22 hi=27

Target: 24

0

0

7

1

9

2

14

3

24

4

32

5

Next: lo=22 hi=27

Target: 24

0

0

7

1

9

2

14

3

24

4

32

5

Next: lo=22 hi=24

Target: 23

0

0

7

1

9

2

14

3

24

4

32

5

Next: lo=22 hi=24

Target: 23

0

0

7

1

9

2

14

3

24

4

32

5

Next: lo=22 hi=24

Target: 23

0

0

7

1

9

2

14

3

24

4

32

5

Next: lo=22 hi=24

Target: 23

0

0

7

1

9

2

14

3

24

4

32

5

Next: lo=24 hi=24

Target: 24

0

0

7

1

9

2

14

3

24

4

32

5

Next: lo=24 hi=24

Key Takeaways

✓ Binary search can be applied on the answer space (possible largest sums), not just array indices.

This insight is hard to see from code alone because the search is on values, not positions.

✓ Prefix sums enable efficient O(log n) checks for valid subarray splits within each binary search iteration.

Understanding prefix sums' role clarifies how subarray sums are computed quickly.

✓ The decision to move low or high depends on whether the current mid allows splitting into m or fewer subarrays.

Seeing the count of subarrays needed at each step concretely shows why the search space narrows.

Practice

1. Given the following code for shipping packages with early stopping feasibility check, what is the final returned minimum capacity for weights = [3, 2, 2, 4, 1, 4] and days = 3?

def can_ship_early_stop(weights, days, capacity):
    day_count = 1
    current_load = 0
    for w in weights:
        if current_load + w > capacity:
            day_count += 1
            if day_count > days:
                return False
            current_load = 0
        current_load += w
    return True

def ship_with_capacity_binary_search_early_stop(weights, days):
    left, right = max(weights), sum(weights)
    while left < right:
        mid = (left + right) // 2
        if can_ship_early_stop(weights, days, mid):
            right = mid
        else:
            left = mid + 1
    return left

print(ship_with_capacity_binary_search_early_stop([3,2,2,4,1,4], 3))

easy

A. 7

B. 6

C. 8

D. 9

Solution

1. Step 1: Trace feasibility check with mid=6

   Check if capacity=6 can ship in 3 days: Day 1: 3+2=5 (ok), next 2 would exceed 6, so day 2 starts Day 2: 2+4=6 (ok), next 1 would exceed 6, so day 3 starts Day 3: 1+4=5 (ok) All packages shipped in 3 days -> feasible.

2. Step 2: Binary search narrows capacity

   Try mid=5 (less than max weight 4, so invalid), mid=7 is next check, which is feasible. The minimal feasible capacity is 7.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Minimal capacity found by binary search is 7 [OK]

Hint: Trace feasibility with mid to find minimal capacity [OK]

Common Mistakes:

• Off-by-one in mid calculation
• Miscounting days in feasibility
• Forgetting to reset current_load

2. You need to compute x raised to the power n efficiently, where n can be a large integer (positive or negative). Which approach guarantees the optimal time complexity for this problem?

easy

A. Use binary exponentiation by repeatedly squaring x and reducing n by half.

B. Iteratively multiply x by itself n times in a loop.

C. Use dynamic programming to store intermediate powers and build up to x^n.

D. Use a greedy approach to multiply by the largest possible power of x at each step.

Solution

1. Step 1: Understand the problem constraints

   We want to compute x^n efficiently for large n, including negative values.

2. Step 2: Identify the optimal approach

   Binary exponentiation (fast exponentiation) reduces the number of multiplications by squaring x and halving n at each step, achieving O(log n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary exponentiation is the classic optimal approach for power calculation [OK]

Hint: Binary exponentiation halves exponent each step [OK]

Common Mistakes:

• Thinking iterative multiplication is efficient for large n
• Confusing DP with binary exponentiation
• Assuming greedy approach works for powers

3. Consider the following buggy code for the Koko Eating Bananas problem. Which line contains the subtle bug that can cause incorrect results on some inputs?

from math import ceil

def can_finish(piles, speed, h):
    hours = 0
    for pile in piles:
        hours += pile // speed  # Line 6
        if hours > h:
            return false
    return true

def minEatingSpeed(piles, h):
    low, high = 1, max(piles)
    while low < high:
        mid = (low + high) // 2
        if can_finish(piles, mid, h):
            high = mid
        else:
            low = mid + 1
    return low

medium

A. Line 9: Returning true when hours <= h

B. Line 3: import statement

C. Line 6: Using floor division instead of ceiling division

D. Line 14: Updating low to mid + 1

Solution

1. Step 1: Identify how hours are calculated

   Line 6 uses floor division (pile // speed), which underestimates hours needed because partial piles still require a full hour.

2. Step 2: Understand impact on feasibility

   Underestimating hours causes can_finish to return true incorrectly, leading to wrong minimum speed.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Replacing floor division with ceiling fixes the bug [OK]

Hint: Hours must be ceil(pile / speed), not floor division [OK]

Common Mistakes:

• Using floor division instead of ceiling
• Misinterpreting feasibility condition

4. What is the time complexity of the optimal binary search algorithm that treats an m x n 2D matrix as a 1D sorted array to search for a target?

medium

A. O(log(m * n))

B. O(m * n)

C. O(m * log n)

D. O(log m + log n)

Solution

1. Step 1: Understand the search space size

   The matrix has m*n elements, treated as a sorted 1D array.

2. Step 2: Apply binary search complexity

   Binary search on an array of size m*n takes O(log(m*n)) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search halves search space each step, log scale [OK]

Hint: Binary search complexity depends on total elements, not rows or columns separately [OK]

Common Mistakes:

• Confusing with O(m*n) brute force
• Thinking binary search per row is O(m log n)
• Adding logs incorrectly as O(log m + log n)

5. Suppose the problem is modified so that packages can be shipped in any order (not necessarily the given order) within the given days. Which of the following approaches correctly finds the minimal ship capacity under this new constraint?

hard

A. Use dynamic programming to assign packages to days minimizing maximum load per day, combined with binary search on capacity

B. Sort packages in descending order and use a greedy bin-packing heuristic combined with binary search on capacity

C. Use a simple greedy approach assigning packages to days in any order without binary search

D. Use the same binary search on capacity with the original feasibility check since order doesn't matter

Solution

1. Step 1: Understand the relaxed constraint

   Packages can be shipped in any order, so the problem becomes a variant of multi-way partition or bin packing minimizing max load.

2. Step 2: Identify correct approach

   Binary search on capacity still applies, but feasibility check requires DP or backtracking to assign packages optimally to days, as greedy heuristics may fail.

3. Step 3: Why other options fail

   Original feasibility check assumes fixed order; greedy heuristics are approximate and may not find minimal capacity.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP feasibility check with binary search needed for unordered assignment [OK]

Hint: Order relaxation requires DP feasibility check, not simple greedy [OK]

Common Mistakes:

• Using original feasibility check ignoring order change
• Assuming greedy suffices
• Ignoring complexity increase