LeetCode Entry

1658. Minimum Operations to Reduce X to Zero

20.09.2023 medium 2023 kotlin

Min suffix-prefix to make an x

1658. Minimum Operations to Reduce X to Zero medium blog post substack image.png

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 variable
  • check 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
    }