Problem statement

https://binarysearch.com/problems/Minimum-Deletions-From-the-Ends-for-Equilibrium/

Solution

I think I saw it on Leetcode, but do not remember where. Reformulate: we need to find the longest subarray, such that it have the same number of ones and zeroes. If we replace 0 with -1, it is the longest subarray with sum zero, for this we can use accumulate sums trick.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums):
        nums = [2*i - 1 for i in nums]
        acc = [0] + list(accumulate(nums))
        d = defaultdict(list)
        for i, x in enumerate(acc):
            d[x] += [i]
        
        return len(nums) - max(d[i][-1] - d[i][0] for i in d)