1658.minimum-operations-to-reduce-x-to-zero.md

1658. Minimum Operations to Reduce X to Zero

Sliding Window

We only remove the elements from the leftmost or rightmost of the array, and we want to minimize the number of removals. Instead of focusing on what to remove, focus on what to keep:

X, X, X, ..., X, X, X, X
^^^^             ^^^^^^^ minimize the removals, sum == x
      |--------| maximize the window, sum = total - x

// For example, x = 10
5, 1, 1, 1, 2, 6, 4, 1, 2, 3   # operations
^^^^^^^^^^^^^                            5
^                       ^^^^             3 * // the minimum operations
                  ^^^^^^^^^^             4

If we remove elements that sum up to x, then the remaining elements will sum up to total - x. So the problem becomes to find the longest subarray that sums up to total - x.

fun minOperations(nums: IntArray, x: Int): Int {
    var total = nums.sum()
    val windowSum = total - x
    // Edge case [1, 1], x = 3, or we can check `left <= right` to avoid the edge case below.
    // if (windowSum < 0) return -1
    var sum = 0
    var left = 0
    var maxLength = Int.MIN_VALUE
    for (right in nums.indices) {
        sum += nums[right]
        /**
         * We need to check `left <= right` because we need to keep at least one element in the window.
         * Check `[1, 1], x = 3` for example. Or we can check if `windowSum < 0` to avoid the edge case.
         */
        while (left <= right && sum > windowSum) {
            sum -= nums[left]
            left++
        }
        if (sum == windowSum) {
            maxLength = maxOf(maxLength, right - left + 1)
        }
    }
    return if (maxLength == Int.MIN_VALUE) -1 else nums.size - maxLength
}

Hash Table + Prefix Sum

TODO: https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/solutions/935935/java-detailed-explanation-o-n-prefix-sum-map-longest-target-sub-array/

Edge Cases

• x > sum(nums): return -1
• x == sum(nums): must remove all elements, return nums.size
• No subarray with sum total - x: return -1