Monotonicity: Sliding Window

Nov 27, 2023 · 5 min read · Algorithms Interview ·

Share on:

A function is monotonic if it preserves the order of its arguments, i.e., if $x \le y$, then $f(x) \le f(y)$. In this post, we examine a class of problems where the argument is an interval. By identifying monotonic functions, we can reduce the number of intervals to enumerate by an order of magnitude, from $O(n^2)$ to $O(n)$. This algorithm is often known as sliding window, because enumerating intervals is like sliding a window across the data.

Problem 1. Max Consecutive Ones

Given an array $A$ of 0's and 1's, find the maximum number of consecutive 1's in $A$ by flipping at most k 0's.

If k=0, the solution is straightforward. Increment the counter when the number is 1 and reset the counter when the number is 0. The largest counter is the answer. If k > 0, the challenge is deciding which 0's to flip. There are two techniques in problem-solving: constructing a solution or enumerating and verifying all possible solutions. Recall the P vs NP problem, where P is the class of problems where an optimal solution can be constructed in polynomial time, and NP is the class of problems where a possible solution can be verified in polynomial time. How can we use the verification technique here?

Given a range A[i:j], if the number of 0's in A[i:j] is no more than k, then j-i+1 is a possible solution. In $O(n)$ time, we can pre-process an array f where f[i] is the total number of 0's in A[0:i]. Verifying whether A[i:j] is a possible solution becomes $O(1)$ by checking $f[j] - f[i-1] \le k$. With $O(n^2)$ ranges to verify, the total time complexity is $O(n^2)$. Can we do better?

Consider two ranges, $A[i:j]$ and $A[i^\prime:j^\prime]$ where $i \le i^\prime \le j^\prime \le j$. If $A[i:j]$ is a solution, then $f[j]-f[i-1] \le k$. According to the definition of $f$, $f$ is monotonically non-decreasing. Thus, $f[i] \le f[i^\prime] \le f[j^\prime] \le f[j]$. Hence, $f[j^\prime] - f[i^\prime -1] \le f[j] - f[i-1] \le k$, indicating that $A[i^\prime:j^\prime]$ is also a solution. Because $j-i \ge j^\prime - i^\prime$, $A[i:j]$ is a better solution than $A[i^\prime:j^\prime]$. This is the monotonic function! The arguments of the function are ranges and the ordering of arguments is based on subarrays. Let's turn this monotonic function into a sliding window algorithm.

Fix $i$ and find the largest $j$ where $A[i:j]$ is a solution. Then increment $i$ by one and repeat. In each iteration, we either increment $i$ or $j$; therefore, the total number of iterations is $O(n)$.

 1func maxConsecutiveOnes(nums []int, k int) int {
 2  n := len(nums)
 3  f := make([]int, n)
 4  f[0] = 1 - nums[0]
 5  for i := 1; i < n; i++ {
 6    f[i] = f[i-1] + (1 - nums[i])
 7  }
 8  countZero := func(l, r int) int {
 9    if l == 0 {
10      return f[r]
11    }
12    return f[r] - f[l-1]
13  }
14
15  // sliding window
16  result := 0
17  for i, j := 0, 0; i < n && j < n; i++ {
18    for ; j < n && countZero(i, j) <= k; j++ {
19      result = max(result, j - i + 1)
20    }
21  }
22  return result
23}

Problem 2. Minimum Number of Replacements to Make Array Continuous

An array of integers is continuous if its numbers can be rearranged to an arithmetic sequence with a common difference of 1. For example, [4, 2, 5, 3] is continuous; but [1, 2, 3, 3, 5, 6] is not. Given an integer array $A$, return the minimum number of replacements needed to make $A$ continuous. In each replacement, any number can be replaced.

Without loss of generality, we can assume there are no duplicates in $A$, and $A$ is sorted. This is because duplicates must be replaced, and whether an array is continuous does not depend on the order of elements.

Finding numbers to replace is the complement of finding numbers to keep. So, how many numbers should we keep in $A$? Following the verification technique, let's examine how to verify a possible solution. Let $A[i:j]$ be the range of numbers to keep. Because $A$ is sorted and unique, there are $A[j]-A[i]+1$ numbers in this range. There are $O(n^2)$ possible $A[i:j]$ ranges, and each range can be verified in $O(1)$ time using $A[j] - A[i] + 1 \le n$. Therefore, the total time complexity is $O(n^2)$. Can we do better?

Consider two ranges, $A[i:j]$ and $A[i^\prime:j^\prime]$ where $i \le i^\prime \le j^\prime \le j$. If $A[i:j]$ is valid, then $A[j^\prime] - A[i^\prime] + 1 \le A[j]-A[i]+1 \le n$, which means $A[i^\prime:j^\prime]$ is also valid. Moreover, $A[j]-A[i]+1 \ge A[j^\prime] - A[i^\prime] + 1$. Thus, $A[i:j]$ keeps more numbers than $A[i^\prime:j^\prime]$, making it a better solution. This is the monotonic function!

 1func minReplacements(nums []int) int {
 2   n := len(nums)
 3   // pre-process: sort and deduplicate
 4   slices.Sort(nums)
 5   a := []int{nums[0]}
 6   for i := 1; i < n; i++ {
 7      if nums[i] == a[len(a)-1] {
 8         continue
 9      }
10      a = append(a, nums[i])
11   }
12
13   // sliding window
14   result := n
15   m := len(a)
16   for i, j := 0, 0; i < m && j < m; i++ {
17      for ; j < m && a[j]-a[i]+1 <= n; j++ {
18         result = min(result, n - (j - i + 1))
19      }
20   }
21   return result
22}

Practice online at

Monotonicity: Sliding Window

Problem 1. Max Consecutive Ones

Problem 2. Minimum Number of Replacements to Make Array Continuous

Appendix: A series of posts on monotonicity.