LC-2439 Medium LeetCode

2439. Minimize Maximum of Array

Array Binary Search Dynamic Programming Greedy Prefix Sum

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 46% Topics: Array, Binary Search, Dynamic Programming, Greedy, Prefix Sum

Reading material

Arrays & Hashing 12 min Binary Search 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

# greedy
class Solution(object):
    def minimizeArrayValue(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def ceil_divide(a, b):
            return (a+b-1)//b

        result = curr = 0
        for i, x in enumerate(nums):
            curr += x
            result = max(result, ceil_divide(curr, i+1))
        return result

Solution from kamyu104/LeetCode-Solutions · MIT