This is something which I was very bad at and recently am able to solve contest questions. More often that not, problem in two pointer isn't visualizing the algorithm, its the part of converting it to code. I want to test this theory out . So, if you find a flaw in this or find a way to make this better, please put it in comments so I'll learn more:)
The basic structure is :
int start = 0, best = 0;
for(int end = 0; end < n; ++end)
{
//include end in the window. The way it is done will depend on the question
//if window is beyond limit, constrict. More often than not this is as simple as ++start;
//update best. eg: best = max(best, end - start + 1). Sometimes you might need to update it on specific conditions.eg: https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/
}
code:
class Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
deque<int> maxq, minq;
int n = nums.size();
int best = 0, start = 0;
for(int end = 0; end < n; ++end)
{
//including end in the window
while(!maxq.empty() && nums[end] >= nums[maxq.back()])
maxq.pop_back();
maxq.push_back(end);
while(!minq.empty() && nums[end] <= nums[minq.back()])
minq.pop_back();
minq.push_back(end);
//constricting window if beyond limit
while(start<end && ((nums[maxq.front()]-nums[minq.front()]) > limit))
{
if(maxq.front() == start)
maxq.pop_front();
if(minq.front() == start)
minq.pop_front();
++start;
}
//update best
best = max(best, end - start + 1);
}
return best;
}
};Sometimes, its the other way where expanding window would fit the condition. eg: https://leetcode.com/problems/minimum-window-substring. In this case, the including end part would remain same. Once you know window is valid, keep increasing start till it becomes invalid, taking best every time.
