20.09.2023
1658. Minimum Operations to Reduce X to Zero medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/345
Problem TLDR
Min suffix-prefix to make an x
Intuition
We can reverse the problem: find the middle of the array to make an arr_sum() - x
. Now, this problem can be solved using a sliding window technique.
Approach
For more robust sliding window:
use safe array iteration for the right border
use explicit
windowSize
variablecheck the result every time
Complexity
Time complexity:
O(n)Space complexity:
O(1)
Code
fun minOperations(nums: IntArray, x: Int): Int {
val targetSum = nums.sum() - x
var windowSize = 0
var currSum = 0
var res = Int.MAX_VALUE
nums.onEachIndexed { i, n ->
currSum += n
windowSize++
while (currSum > targetSum && windowSize > 0)
currSum -= nums[i - (windowSize--) + 1]
if (currSum == targetSum)
res = minOf(res, nums.size - windowSize)
}
return res.takeIf { it < Int.MAX_VALUE } ?: -1
}