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 K-1) 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+K-1], 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.