2439. Minimize Maximum of Array - Explanation

1. Binary Search

class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        def isValid(maxVal):
            prefix_sum = 0
            for i in range(len(nums)):
                prefix_sum += nums[i]
                if prefix_sum > maxVal * (i + 1):
                    return False
            return True

        left, right = 0, max(nums)
        while left < right:
            mid = left + (right - left) // 2
            if isValid(mid):
                right = mid
            else:
                left = mid + 1

        return left

Time & Space Complexity

Time complexity: $O(n \log m)$
Space complexity: $O(1)$ extra space.

Where $n$ is the size of the array $nums$ and $m$ is the maximum value in the array.

2. Prefix Sum + Greedy

class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        res = total = nums[0]

        for i in range(1, len(nums)):
            total += nums[i]
            res = max(res, math.ceil(total / (i + 1)))

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.