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 look at a class of problems where the argument is an interval. By identifying monotonic functions, we can reduce number of intervals to enumerate by an order of magnitude, from $O(n^2)$ to $O(n)$. The algorithm is often known as sliding window, because enumerating intervals is like sliding windows.

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 come: constructing a solution or enumerating and verify all possible solutions. Recall the P vs NP, 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. So, 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 a monotonic 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]$. That is the monotonic function! The arguments of the function are ranges and the ordering of arguments is subarrays. Let's turn the monotonic function into a sliding window algorithm.

Fix $i$, find the largest $j$ where $A[i:j]$ is a solution. Then increment $i$ by one and repeat. In each enumeration, we either increment $i$ or $j$, therefore the total number of enumerations 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 generosity, 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 technique of verification, let's look at 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 to keep. There are $O(n^2)$ possible $A[i:j]$ ranges, and each range is verified in $O(1)$ 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. That 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.