Question 3

Given an array of numbers N and an integer k, your task is to split N into k partitions such that the maximum sum of any partition is minimized. Return this sum.

For example, given N = [5, 1, 2, 7, 3, 4] and k = 3, you should return 8, since the optimal partition is [5, 1, 2], [7], [3, 4].

Approach

  1. Start by sorting the array in descending order. This helps group larger numbers together, making it easier to control the maximum partition sum.
  2. Determine the possible range for the maximum partition sum.
    The lowest possible value is the largest element in the array.
    The highest possible value is the sum of all the elements in the array.
  3. Employ binary search within this range. For each ‘mid’ value:
    a. Try dividing the array into partitions such that no partition sum exceeds ‘mid’.
    b. If you can successfully divide the array, that means ‘mid’ is a possible maximum partition sum. Try to reduce ‘mid’ further (search in the lower half of the range).
    c. If you cannot divide the array, this means ‘mid’ is too small. Explore larger maximum partition sums (search in the upper half of the range).
  4. Continue the binary search until you find the smallest possible ‘mid’ that successfully partitions the array.

Pseudo Code

Code
FUNCTION min_max_partition(nums, k)
   SORT nums in descending order 
   low = largest_number_in(nums)
   high = sum_of_all_elements_in(nums)

   WHILE low < high
       mid = (low + high) / 2 

       IF can_partition(nums, k, mid) 
           high = mid  
       ELSE 
           low = mid + 1

   RETURN low 

FUNCTION can_partition (nums, k, max_allowed_sum)
   current_partition_sum = 0
   num_partitions = 1  

   FOR EACH num IN nums
        IF current_partition_sum + num > max_allowed_sum
            num_partitions = num_partitions + 1 
            current_partition_sum = num  
        ELSE
            current_partition_sum = current_partition_sum + num

   RETURN num_partitions <= k
Explanation
  1. min_max_partition
    • We sort the array for potential optimization.
    • We establish the search space between the largest number and the total sum.
    • The binary search loop iteratively adjusts the low and high boundaries, using the can_partition helper function to evaluate the feasibility of a given mid value as the target maximum partition sum.
  2. can_partition
    • This function tracks the current partition’s sum.
    • If adding a number would exceed the max_allowed_sum, it starts a new partition.
    • It returns True if the array can be divided into ‘k’ or fewer partitions.

Implementation

Golang
package main

import (
	"fmt"
	"sort"
)

func minMaxPartition(nums []int, k int) int {
	// Helper function to check if a partition is possible with a given maximum sum
	canPartition := func(maxSum int) bool {
		subarrays := 0
		currSum := 0
		for _, num := range nums {
			if currSum+num > maxSum {
				subarrays++
				currSum = num // Reset current sum for the new subarray
			} else {
				currSum += num
			}
		}
		return subarrays+1 <= k // Account for the final subarray
	}

	// Sort the array in descending order
	sort.Slice(nums, func(i, j int) bool { return nums[i] > nums[j] })

	low := nums[0] // Lowest possible maximum sum
	high := 0      // Highest possible maximum sum
	for _, num := range nums {
		high += num
	}

	// Binary search to find the minimum maximum sum
	for low < high {
		mid := low + (high-low)/2
		if canPartition(mid) {
			// Can form partitions using 'mid', try finding a lower maximum sum
			high = mid
		} else {
			// 'mid' is too small, increase the lower bound
			low = mid + 1
		}
	}

	return low
}

func main() {
	nums := []int{5, 1, 2, 7, 3, 4}
	k := 3
	result := minMaxPartition(nums, k)
	fmt.Println(result) // Output: 8
}