There are a lot of interesting connected ideas here on prefixes and monoticity and "imposing" a bit of monoticity onto a problem which actually doesn't ask for it.
It feels like a sliding window, but sliding windows only work on window properties that are monotone with respect to expanding the window.
The unifying move behind a huge chunk of "array algorithm" problems is:
Turn a messy global problem into local bookkeeping where cancellation, balance, or repetition reveals structure.
There are a lot of invariants. That's the thing that we are exploiting. That's why they all feel similar.
class Solution:
def findMaxLength(self, nums):
# Map to store (prefix_sum: first_index_it_occurred)
# Initialize with 0: -1 to handle subarrays starting from index 0
indices = {0: -1}
max_len = 0
count = 0
for i, num in enumerate(nums):
# Treat 0 as -1 and 1 as 1
count += 1 if num == 1 else -1
if count in indices:
# Calculate length: current index - first occurrence of this sum
max_len = max(max_len, i - indices[count])
else:
# Only store the first occurrence to maximize the distance/length
indices[count] = i
return max_len