Solution
Approach 1: Greedy + Events
Intuition
If the leftmost element is a 0, we must flip the subarray starting at index 0. Similarly, if the leftmost element is a 1, we should not flip the subarray starting at index 0. This proves we can proceed in a greedy manner: after finding out whether we have to flip the first subarray (positions 0 to K1) or not, we can consider the array with the first element (value 1) removed, and repeat this process.
We can do better. Every time we flip a subarray A[i], A[i+1], ..., A[i+K1]
, we can consider this as two "events", one 'opening event' at position i
that marks the start of the subarray, and one 'closing event' at position i+K
that marks the end of the subarray. Using these events, we always know how many overlapping flipped subarrays there are: its simply the number of opening events minus the number of closing events.
Algorithm
When we flip a subarray, let's call the set of indices we flipped an interval. We'll keep track of flip
, the number of overlapping intervals in our current position. We only care about the value of flip
modulo 2.
When we flip an interval starting at i
, we create a hint for a closing event at i+K
telling us to flip our writing state back.
Please see the inline comments for more details.
Complexity Analysis

Time Complexity: , where is length of
A
. 
Space Complexity: .
Analysis written by: @awice.