Introduction
In this post, I gather common problems that utilize sliding windows techniques to solve dynamic programming problems.
Concepts
Sliding windows arise from the need to optimize time complexity to O(n).
Sliding windows are defined by left, and right boundary; thus, the techniques are sometimes called two pointers.
Common questions to sliding windows usually involves questions about subarray.
- Find max/min length of subarray that satisfies certain conditions. The question could even be about something else, but basically means finding subarray length.
- Find number of subarrays that satisfies certain conditions.
- Find a fix length subarray that satisfies certain conditions.
The common code template for [variable size] sliding windows is:
function fn(arr):
left = 0
for (int right = 0; right < arr.length; right++):
Do some logic to "add" element at arr[right] to window
while WINDOW_IS_INVALID:
Do some logic to "remove" element at arr[left] from window
left++
Do some logic to update the answerThe common code template for [fix size] sliding windows is:
function fn(arr, k):
curr = some data to track the window
// build the first window
for (int i = 0; i < k; i++)
Do something with curr or other variables to build first window
ans = answer variable, probably equal to curr here depending on the problem
for (int i = k; i < arr.length; i++)
Add arr[i] to window
Remove arr[i - k] from window
Update ans
return ansProblem Sort Array by Parity
We will start practicing with an easy problem Sort Array By Parity that utilizes ingenuous solution of 2 pointers. Using 2 pointers, we can achieve time complexity O(n) and space complexity O(1)
Solution 1:
- choose
left= right = nums[0]. - performs logic such that items on the left of
leftare even. We use indexrightto check if the value is even or odd.- use for loop, increment
rightalways. - while WINDOW_IS_INVALID: the invalid condition is when
nums[right] %2 ==0. then incrementleft
- use for loop, increment
class Solution {
public:
vector<int> sortArrayByParity(vector<int>& nums) {
int left=0;
for(int right=0;right<nums.size();right++){
if(nums[right]%2==0){
swap(nums[right],nums[left]);
left++;
}
}
return nums;
}
};Solution 2: a much less intuitive solution.
- choose
left=0andright = nums.size()-1 - if a value
nums[right]is odd, keep it where it is, thus we decrementright. - if nums[left] is odd, and nums[right] is even, we swap them.
class Solution {
public:
std::vector<int> sortArrayByParity(std::vector<int>& nums) {
int right = nums.size() - 1;
for (int left = 0; left < right; ++left) {
while (left < right && nums[right] % 2 == 1) {
right--;
}
if (left < right && nums[left] % 2 == 1 && nums[right] % 2 == 0) {
std::swap(nums[left], nums[right]);
}
}
return nums;
}
};Notes: solution 2 slightly rearranges the relative positions of odd to odd numbers, even to even numbers. In addition, the if case is slightly redundant, we only need if(left<right)
Problem Remove Item equal to Val in Array
Another 2 pointer problem Remove Element. Note that in this problem, we don't actual remove items off the memory. Instead, we return size of the new array. We use the left pointer as the iterator to update the array. We use the right pointer to traverse the original array and look for items equal to val.
Upon revising the logic, we will actually do nothing when nums[right] == val, and thus have the following solution:
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int ans=0;
for (int right=0,left=0; right< nums.size() && left< nums.size(); right++ ){
if (nums[right] == val){
}
else {
nums[left] = nums[right];
left++;
ans++;
}
}
return ans;
}
};Problem Removes Duplicated in Sort Array
The problem utilizes basic usages of 2 pointers to perform in-place operations on an array.
The main idea is to use 2 pointers:
- left to update the array at
arr[left]with non-duplicated values, and to return final size. - right to traverse and check for duplicated values.
The tricky part is that it is necessary to set up left=1 and right =1 at the beginning, although it was more intuitive for me to set left=0.
Code:
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int left = 1;
int right = 1;
for (right; right<nums.size(); right++){
if (nums[right] != nums[right-1]){
nums[left] = nums[right];
left++;
}
}
return left;
}
};Problem Squares of a Sorted Array
The problem Squares of a Sort Array requires squaring every element in the array and sort the array. If we do the easy way, that includes 2 steps, square the items, taking time complexity O(n), and sort the array with Merger sort or Insertion sort, taking time complexity O(nLogn), there is still room to optimize the solution. The following explains using 2 pointers technique to solve the problem.
- the 2 pointers technique could only be applied if the input
numsarray is sorted in ascending order. - create an array to store result. The input array is not changed.
- create 2 pointer
left = 0andright=nums.size()-1, the sliding window is initialized at the whole input array.leftandrightkeeps track of the index of the original array whose items should be copied to resulting array.
- loop through the input array:
- compare the item at
nums[left]andnums[right] - while WINDOW_IS_INVALID:
- if
abs(nums[left]) < abs(nums[right])updatenums[i], and shift right inward. - otherwise, do the opposite
- if
- compare the item at
The following illustrates how the result array and sliding window changes over iterations. Green depicts the sliding windows.
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
vector<int> result(n);
int left = 0;
int right = n - 1;
for (int i = n - 1; i >= 0; i--) {
int square;
if (abs(nums[left]) < abs(nums[right])) {
result[i] = nums[right]*nums[right];
right--;
} else {
result[i] = nums[left]*nums[left];
left++;
}
// result[i] = square;
}
for (int i : result)
cout<<i<<" ";
return result;
}
};Problem Permutation in String
Leetcode problem: Permutation in String
We have 2 string and want to check if any permutation of string2 could match string1. We could use backtracking logic to create a Permutation set of n characters from string2, where n is the size of string1.
A better solution is using sliding window. We use a sliding window to compare the substrings of string2 with string1.
- edge case:
if string1.length() > string2.length returns false. - sliding window has the size of string1.
- right boundary:
index+string1.length() - left boundary:
index
- right boundary:
- sliding window compares the frequency of characters in the substrings contained within the window. Because we are comparing permutation, not exact strings.
- freqStr1[26] stores the frequency of characters in string1. 26 is due to 26 characters.
- freqStr2[26] stores the frequency of characters in string2.
- while WINDOW_IS_INVALID: there is no match between substrings
Str1andStr2- increment both left and right.
- for every position in the sliding windows, we have to update freqStr2[26].
First, the frequency arrays are initialized for every characters from index=0 to index= string1.size(). In addition, s1[i] - 'a' converts the character to int.
std::vector<int> freqStr1(26, 0);
std::vector<int> freqStr1(26, 0);
for (int i = 0; i < s1.length(); i++) {
freqStr1[s1[i] - 'a']++;
freqStr1[s2[i] - 'a']++;
}Since the sliding windows only changes with both left and right incremented by 1, we only need to update the frequency arrays for the characters at the boundaries:
int left= index;
int right = index + s1.length();
freqStr2[s2[right] - 'a']++;
freqStr2[s2[left] - 'a']--;Code:
class Solution {
bool match(vector<int>& freqStr1, vector<int>& freqStr2){
for (int i=0; i<26;i++){
if (freqStr1[i] != freqStr2[i])
return false;
}
return true;
}
public:
bool checkInclusion(string s1, string s2) {
if (s1.length() > s2.length())
return false;
vector<int> freqStr1(26, 0);
vector<int> freqStr2(26, 0);
for (int i = 0; i < s1.length(); i++) {
freqStr1[s1[i] - 'a']++;
freqStr2[s2[i] - 'a']++;
}
for (int index=0; index < s2.length()-s1.length();index++){
if (match(freqStr1, freqStr2)) return true;
else{
// condition doesn't match, move left and right toward the right.
// thus add character on the right to freq count
// remove character on the left from freq count.
int left= index;
int right = index + s1.length();
freqStr2[s2[right] - 'a']++; // update freq of the character at right boundary
freqStr2[s2[left] - 'a']--; // update freq of the character at left boundary
}
}
return match(freqStr1, freqStr2); // must add final check for last window.
}
};Problem Minimum Size of Subarray sum
The problem, Minimum Size Subarray Sum, could be solved with Topdown- Recursive solution or Iterative solution as explained in Dynamic Programming – From Recursive to Iteration – Using 2D DP array.
- The recursive solution explores the choice of picking or not picking an item to add to subarray.
- The iteration solution constructs a 2 day arrays and calculate subarray sum.
The iteration solution is not much different from a brute force approach, with the only exception that we skip adding more item to subarray when the sum is greater than target value. Regardless, we have worst case time complexity as O(n^2).
With sliding windows, we could have time complexity as O(n)m and worst case as O(2n). It is also more intuitively:
- using left and right as boundary of the subarray.
- increment right, as we loop from 0 to array.size(), add items to subarray, and add up sum.
- if the sum is equal or greater than target value, then we have the target subarray:
- update min size to get result.
- move up left and update new subarray sum until the sum is less than target. It means we look for a new subarray whose sum is equal or greater than the target value.
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int result = INT_MAX;
int left=0, right=0, sum=0;
for (right; right < nums.size(); right++ ){
sum += nums[right];
if (sum <target){
// right++; // add items to subarray
}
while (sum >= target){
result = min(result, right - left + 1);
// make new subarray starting from left
sum -=nums[left];
left++;
}
}
return result == INT_MAX ? 0 : result;
}
};