1658. Minimum Operations to Reduce X to Zero

class Solution:
    def minOperations(self, A: List[int], x: int) -> int:
        """tc O(N) sc O(N)
        find subarray A(l:r] s.t. its length is max and total - sum(A(l:r]) == x => total - x ==  sum(A(l:r])  => psum(A[r]) - psum[A[l]]
        => we keep record a presum with its [no have to be first](presum is unique since A[i] > 0 ) idx 
        check if psum(A[r]) - (total-x) exist in hmap.  
                    if yes, possible windows length is r-l  (left exclusive, right inclusive)
                    
        """
        max_w = -1 # goal is to find max windowsize , res = len(A) - max_w
        total_x = sum(A) -x
        if total_x==0 :
            return len(A)
        presum_idx = {0:-1}# zero offset
        psum = 0
        for i,a in enumerate(A):
            psum += a 
            if psum - total_x in presum_idx:
                max_w = max(max_w,i-presum_idx[psum - total_x])
            presum_idx[psum] = i # no need to get fisrt idex that sum is psum because psum is singular increasing  
        return len(A) - max_w if max_w != -1 else -1