The pattern of question can be solved by Two Pointers algorithms is

Return the length of the longest contiguous subarray [u,v] of array A that [u,v] meets the requirement X. With X is a requirement such that: if [u,v] doesn't meet X, then [u,v'] doesn't meet X too (v' > v).

Example:

  • Given an array A of 0s and 1s, we may change up to K values from 0 to 1.
    Return the length of the longest (contiguous) subarray that contains only 1s.
  • Given a string s, find the length of the longest substring t that contains at most 2 distinct characters.
  • Given a string, find the length of the longest substring without repeating characters.

The naive algorithm is considering all subarray [u,v] (0 <= u <= v < n) and check if [u,v] meet X. The complexity is O(n^2).

    int u = 0, v = 0;
    for(u = 0; u < n; u++)
        for(v = u; v < n; v++)
            if (ok(fx(u,v), X) res = max(res, v - u + 1);

However, X has a property that if [u,v] doesn't meet requirement X then [u,v'] will not meet X with v' > v. Take advantage of this property:

  • we can stop v as soon as [u,v] no longer meet requirement X
    int u = 0, v = 0;
    for(int u = 0; u < n; u++)
        for(int v = u; v < n; v++)
            if (ok(fx(u,v), X) res = max(res, v - u + 1);
            else break;
  • after we stop v (by break), [u, v-1] is the last valid subarray we consider (lenght = v-u), we no need to consider all the subarrays [u, k], where k < v, because k - u + 1 < v - u + 1 anyway, i.e. we cannot get a better outcome when considering [u,k] (k < v).

Step 1: Initially i = j = 0
Step 2: Try to extend i as far as possible such that subarray [j,i] fullfils the requirement X.
Step 3: When i reaches the point where subarray [j,i] doesn't meet requirement X, we stop and increase j until [j,i] meet requirement X again. Then we repeat Step 2. Until i reach size of the array.

The common code for all of this type of questions:

  • a is the array we concern
  • fx(u,v) is the function of subarray [u,v] we consider against condition X.
    int n = a.size();
    int i = 0, j = 0;
    // calculate fx(0,0)
    while (i < n) {
    // if meet the requirement X
        if (ok(fx(j, i), X)) {
            res = max(res, i - j + 1);
            i++;
            if (i < n) {
                // calculate fx(j,i);
            }
        } else {
            j++;
            // calculate fx(j,i);
        }
    }

I prefer calling this technique Snake technique because the subarray [i,j] is moving like a snake during the algorithm.

Note that only when requirement X has the above mentioned property, we can apply this technique. For example, we cannot use this technique for the following problem:

Given a binary array, find the longest contiguous subarray that has number of 1 strictly greater than number of 0. (https://leetcode.com/problems/longest-well-performing-interval/)

0 1 2 3 4 5 6 7
0 1 0 0 1 1 1 1

We can easily see in this example, subarray [0,2] (0, 1, 0) does not meet requirement X but [0,7] (0, 1, 0, 0, 1, 1, 1, 1) still meet requirement X.

Example 1: Given an array A of 0s and 1s, we may change up to K values from 0 to 1. Return the length of the longest (contiguous) subarray that contains only 1s.

This question is equivalent to Find the longest contiguous subarray that has at most K 0. In this case:

  • Condition X is "has at most K 0"
  • fx(u,v) will be number of 0 in subarray [u,v]
  • ok(fx(u,v), X) will be fx(u,v) <= K

We have the following code:

    int longestOnes(vector<int>& a, int K) {
        int n = a.size();
        int i = 0, j = 0, res = 0;
        int num = a[i] == 0 ? 1 : 0;
        while (i < n) {
            if (num <= K) {
                res = max(res, i - j + 1);
                i++;
                if (i < n) num += (a[i] == 0);
            } else {
                num -= (a[j] == 0);
                j++;
            }
        }
        return res;
    }
Example 2: Given a string s , find the length of the longest substring t that contains at most 2 distinct characters.
  • Condition X is "contains at most 2 distinct characters"
  • fx(u,v) is calculated a bit more complicated: we need to maintain a set A of distinct character of subarray [u,v], and to update A, we use a map count to count frequency of each character in A
  • ok(fx(u,v), X) will be A.size() <= 2
    int lengthOfLongestSubstringTwoDistinct(string s) {
        unordered_set<char> a;
        unordered_map<char, int> count;

        int n = s.size();
        if (n == 0) return 0;
        int i = 0, j = 0, res = 0;
        a.insert(s[0]);
        count[s[0]] = 1;
        while (i < n) {
            if (a.size() <= 2) {
                res = max(res, i - j + 1);
                i++;
                if (i < n) {
                    a.insert(s[i]);
                    count[s[i]]++;
                }
            } else {
                count[s[j]]--;
                // only remove s[j] from a if count[s[j]] == 0
                if (count[s[j]] == 0) a.erase(s[j]);
                j++;
            }
        }        
        return res;
    }

The key here is to determine X, fx(u,v) and the way to calculate fx(u,v).

Some problems can be solved by this Snake technique: