Monotonicity: Sliding Window
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; [1, 2, 3, 3, 5, 6] is not. Given an integer array $A$, return the minimum number of replacements 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
- Leetcode 1004. Max Consecutive Ones III
- Leetcode 2009. Minimum Number of Operations to Make Array Continuous
- Leetcode 3. Longest Substring Without Repeating Characters
- Leetcode 424. Longest Repeating Character Replacement
Appendix: A series of posts on monotonicity.
- Monotonicity: Find 1-3-2 Pattern
- Monotonicity: Find Largest Subarrays for Each Array Element
- Monotonicity: Find the K-th number in two sorted arrays
- Monotonic Stack: Steps to Make Array Non-decreasing