leetcode: Minimum Operations to Reduce X to Zero

problem

• https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/

Prefix sum with Two Pointers

class Solution {
    fun minOperations(nums: IntArray, x: Int): Int {
        val size = nums.size
        // prefix array starts with index 1
        val prefix = IntArray(size + 1) { 0 }
        // calculate prefix array
        for (i in 1..size) {
            prefix[i] = prefix[i - 1] + nums[i - 1]
        }
        
        val total = prefix[size]
        var start = 0
        var end = 1
        var answer = Int.MAX_VALUE
        // find maximum sub array
        while (end <= size && start <= end) {
            val sub = prefix[end] - prefix[start]
            if (sub == total - x) {
                // found!
                answer = minOf((size - end) + start, answer)
                // forward
                end++
                start++
            } else if (sub < total - x) {
                // need bigger value
                end++       
            } else {
                // need to reduce different between start and end
                start++
            }
        }
        return if (answer == Int.MAX_VALUE) -1
        else answer
    }
}

Prefix sum with Hash Table

class Solution {
    fun minOperations(nums: IntArray, x: Int): Int {                
        // target of prefix subArray
        val target = nums.sum() - x
        // testcase: sum of nums is equal to x
        if (target == 0) return nums.size
        
        val table = mutableMapOf<Int, Int>()
        // testcase: (1 1 4) 2 3 -> () means prefix
        table[0] = -1
        var sum = 0
        var answer = Int.MIN_VALUE
        // find largest prefix subArray                
        nums.forEachIndexed { index, num -> 
            // accumulate number
            sum += num
            // find start of subArray
            val temp = table[sum - target]
            if (temp != null) {
                answer = maxOf(answer, index - temp)    
            }
            // store index of prefix sum
            table[sum] = index
        }
        return if (answer == Int.MIN_VALUE) -1
        else nums.size - answer
    }
}