2439.minimize-maximum-of-array.md

2439. Minimize Maximum of Array

Hints

• What happens if you always move excess from right to left?
• Can you check if a given maximum value is feasible using a greedy simulation?
• Is there a way to relate the answer to prefix sums or averages?

Breakdowns

1. Can we check if a given value is feasible as the maximum after all operations?

Try simulating the process from right to left, moving excess to the left. If the first element can be kept ≤ threshold, it's feasible.

2. Is there a direct formula for the answer?

Notice that after all possible operations, the array becomes as flat as possible. The answer is the maximum of all prefix averages (rounded up).

Key Insights

• The operation allows you to move any excess from right to left, so the leftmost elements can absorb all surplus.
• The minimum possible maximum is determined by the largest prefix average (since you can't make the prefix sum smaller than its average).
• (TODO) There is also a direct greedy solution using prefix averages, which is more efficient and elegant.

Binary Search

• Monotonicity: If a value is feasible, any larger value is also feasible.
• Lower bound: The minimum value in the array would be acceptable. (Consider the single element case)
• Upper bound: The maximum value in the array. (Without any modification)
• Feasibility: There are two ways to check if a value is feasible:
  • Check 1: Check if we have enough buffer to absorb all excess.
  • Check 2: Simulate moving excess from right to left and check if the first element stays ≤ threshold.

fun minimizeArrayValue(nums: IntArray): Int {
    var left = nums.min()
    var right = nums.max()
    while (left <= right) {
        val middle = left + (right - left) / 2
        val feasible = check(nums, middle)
        if (feasible) {
            right = middle - 1
        } else {
            left = middle + 1
        }
    }
    return left
}

// Check 1: Check if we have enough buffer to absorb all excess.
private fun check(nums: IntArray, threshold: Int): Boolean {
    var buffer = 0L
    for (num in nums) {
        buffer += (threshold - num).toLong()
        if (buffer < 0L) return false
    }
    return true
}

// Or alternatively, check 2: Simulate moving excess from right to left and check if the first element stays ≤ threshold.
private fun check2(nums: IntArray, threshold: Int): Boolean {
    var excess = 0L
    for (i in nums.size - 1 downTo 1) {
        if (nums[i] + excess > threshold) {
            excess = nums[i] + excess - threshold
        } else {
            // We can't pass negative excess to the left because:
            // 1. The operation only allows moving excess from right to left
            // 2. If we have a deficit (negative excess), we can't "borrow" from the left
            // 3. The left elements can only absorb surplus, not create it
            excess = 0L
        }
    }
    return nums[0] + excess <= threshold
}

• Time Complexity: O(n log(max(nums)))
• Space Complexity: O(1)

Prefix Average (Optimal Greedy)

TODO: Understand this approach later.

Key idea: The answer is the maximum of all prefix averages (rounded up).

fun minimizeArrayValue(nums: IntArray): Int {
    var maxAvg = 0L
    var prefixSum = 0L
    for (i in nums.indices) {
        prefixSum += nums[i]
        val avg = (prefixSum + i) / (i + 1) // ceil division
        maxAvg = maxOf(maxAvg, avg)
    }
    return maxAvg.toInt()
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Edge Cases

• All elements are the same: The answer is that value.
• Large values at the end: The excess will be pushed to the leftmost element.
• Single element: The answer is the element itself.
• Very large input: Use Long for prefix sum to avoid overflow.

Pitfalls

• Forgetting to use Long for prefix sum or excess, causing overflow.
• Not resetting excess to 0 when redistributing in the binary search check.
• Off-by-one error in prefix average calculation (should use (prefixSum + i) / (i + 1) for ceiling division).

WA

fun minimizeArrayValue(nums: IntArray): Int {
    // Binary search bounds are correct - we search between min and max values
    var left = nums.min()
    var right = nums.max()
    while (left <= right) {
        val middle = left + (right - left) / 2
        val feasible = check(nums, middle)
        if (feasible) {
            right = middle - 1
        } else {
            left = middle + 1
        }
    }
    return left
}

private fun check(nums: IntArray, threshold: Int): Boolean {
    // ISSUE 1: Modifying input array directly is dangerous and can affect future checks
    // ISSUE 2: The logic doesn't properly handle the case where we need to move values from right to left
    var max = nums.last()
    for (i in nums.size - 1 downTo 0) {
        if (i > 0) {
            while (nums[i - 1] < nums[i]) {
                nums[i]--
                nums[i - 1]++
            }
        }
        max = maxOf(max, nums[i])
        if (threshold < max) return false
    }
    return true
}