Sliding window

Pseudocode for the sliding window algorithm:

def fun(arr):
	n = len(arr)
	l = 0
	r = 0
	ans = 0
	while r < n:
		# update state of the current window

		# contract window until we have a valid one
		while current window is invalid:
			# update state of the current window
			l += 1

		ans = max(ans, r - l + 1)

		# expand the window
		r += 1

	return ans

Example

Given a binary array nums and an integer k, return the maximum number of consecutive 1’s in the array if you can flip at most k 0’s (https://leetcode.com/problems/max-consecutive-ones-iii).

A key insight here is that we can translate this question into returning the longest window that has <= k 0’s, because then we can flip all the 0’s to be 1’s (this is a similar trick to https://leetcode.com/problems/max-consecutive-ones-ii/).

First, we solve it with brute force:

def fun(arr, k):
	n = len(arr)
	ans = 0
	for l in range(n):
		for r in range(l, n):
			nz = 0
			for i in range(l, r + 1):
				if arr[i] == 0:
					nz += 1

			if nz <= k:
				ans = max(ans, r - l + 1)
	return ans

The time complexity is O(n^3) (it’s very similar to https://leetcode.com/problems/maximum-subarray/).

Now we apply the sliding window template:

def fun(arr, k):
    n = len(arr)
    l = 0
    r = 0
    ans = 0
    nz = 0
    while r < n:
		# update state of the current window
        if arr[r] == 0:
            nz += 1

        # contract window until we have a valid one
        while nz == k+1:
            # update state of the current window
            if arr[l] == 0:
                nz -= 1
            l += 1

        ans = max(ans, r - l + 1)

        # expand the window
        r += 1

    return ans

Note that in the worst case the left pointer visits each element of the array once and the right pointer visits each element of the array once, so the time complexity is O(n).

Example (2)

https://leetcode.com/problems/maximize-the-confusion-of-an-exam/

def fun(arr, k):
    n = len(arr)
    l = 0
    r = 0
    ans = 0
    n_true = 0
    n_false = 0
    while r < n:
        # update state of the current window
        if arr[r] == 'T':
            n_true += 1
        else:
            n_false += 1
            
        # contract window until we have a valid one
        while n_true > k and n_false > k:
            # update state of the current window
            if arr[l] == 'T':
                n_true -= 1
            else:
                n_false -= 1
            l += 1
            
        ans = max(ans, r - l + 1)
        
        # expand the window
        r += 1
        
    return ans