Problem statement

https://binarysearch.com/problems/Remove-Sublist-to-Reach-Equilibrium/

Solution

Use cumulative sum: we need to find the shortest subarray with sum equal diff: difference between number of values more and less than k in whole array.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums, k):
        diff = sum(x > k for x in nums) - sum(x < k for x in nums)
        if diff == 0: return len(nums)
        d, last, ans = {0:-1}, 0, len(nums)
        
        for i, num in enumerate(nums):
            if num > k: last += 1
            if num < k: last -= 1
            if last - diff in d: ans = min(ans, i - d[last - diff])
            d[last] = i
        return len(nums) - ans