~/leetcode$cat1658. Minimum Operations to Reduce X to Zero

I’m thinking of making a prefix and a suffix sum list where prefix[i] and suffix[i] represents the sum of the values up to index i for each respective direction.

Once we get this, for each prefix[i], we can binary search through suffix to find the index at where prefix[i] + suffix[j] = value. The number of operations would then be i + j. We can return the min i + j that we find.

Post-submission Note

After analyzing, leetcode showed that there is a O(n) solution if we use two pointers - which make sense since we can just binary search through the prefix and suffix.

class Solution:
    def binarySearch(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums) - 1

        while (l <= r):
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid

            if nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1

        return -1

    def minOperations(self, nums: list[int], x: int) -> int:
        n = len(nums)
        prefixes = []
        suffixes = []
        curr_prefix = 0
        curr_suffix = 0
        for i in range(n):
            curr_prefix += nums[i]
            curr_suffix += nums[n - (1 + i)]
            prefixes.append(curr_prefix)
            suffixes.append(curr_suffix)

        min_op = inf
        a = self.binarySearch(suffixes, x)
        if a != -1:
            min_op = min(a + 1, min_op)
        for i in range(n):
            prefix = prefixes[i]
            if prefix == x:
                min_op = min(i + 1, min_op)

            j = self.binarySearch(suffixes, x - prefix)
            if j == -1:
                continue
            if (n - j - 1) <= i:
                break

            min_op = min(i + j + 2, min_op)

        if min_op == inf:
            return -1
        return min_op

Time Complexity: O(n log n)

Space Complexity: O(n)

Time Taken: 17m 11s

Runtime: 1306 ms

Memory: 34 MB

Tests Passed: 97/97