The Caterpillar method is a name for a popular way of solving a certain set of algorithmic tasks. The idea is to check array elements in a way that is reminiscent, of the movement of a caterpillar (animal). The caterpillar crawls through the array. Unlike the real caterpillar, the software caterpillar begins with zero length, with the front and back legs at the array element of index 0. For simplicity, assume the software caterpillar has two pairs of legs: the front pair of legs and the back pair of legs. Both front legs would move forward at the same time, and both back legs would move forward at the same time. However, the front pair of legs cannot move forward to the next index, while the back pair of legs are also moving forward to the next index. In other words, the caterpillar cannot jump (cannot hop). 

While the software caterpillar is crawling the array, its length can be increasing or decreasing. A variable, front should be remembering the position (index) of the front legs, and another variable, back should be remembering the position (index) of the back legs.

Problem Example

You are given a sequence a₀ , a₁ , . . . , a_n−1 (1 ≤ a_i ≤ 10⁹ ) that contains a contiguous (continuous) sub-sequence, whose sum of elements equals 12. Let s be 12. The array is:

 It can be seen by inspection, that from index 2 (back legs) to index 4 (front legs), the total (sum) of the consecutive elements, 7, 4 and 1 is 12. No other sub-sequence before this (from the left) has the total of 12. The elements (values) are assumed to have been arranged at random. The general algorithm for the caterpillar method is as follows:

- If it is possible, move the right end (front) forward, and increase the size (length) of the caterpillar by one unit;

- otherwise, move the left end (back) forward, and decrease the size of the caterpillar by one unit. 

Solving the Above Problem

The aim (objective) is to find a sub-sequence, whose sum (total) is equal to 12. At the beginning, front = 0 and back = 0, and the length of the caterpillar is 0. The value of 6, becomes the only total. It is not equal to 12. So the front legs go to index 1, and the length of the caterpillar becomes two (for index 0 and index 1). 6 + 2 = 8. Eight is not yet equal to 12. So the front legs go to index 2, while the back legs remain at index 0. The length of the caterpillar is now three. 6 + 2 + 7 = 15. This is greater than 12.

The strategy is that, for the caterpillar to crawl, it would move the front legs ahead by one step, if the current sum is less than s = 12. If the sum then becomes 12, both the movements of the front and back legs stop. If the current sum is greater than 12, it would move the back legs to reduce the size (length of caterpillat) and the sum. 

Increasing the length of the caterpillar from this point, where sum is greater than 15, does not help (since the sum becomes even higher). So the back legs have to be moved forward by one step (index), decreasing the current sum (total), and hoping that the new sum would be 12. When that happens, the new sum becomes 2 + 7 = 9, which is less than 12. So the front legs have to be moved forward, by one step, while the back legs remain at index 1, hoping that the new sum would be 12. The new sum becomes 2 + 7 + 4 = 13, which is above 12. The back legs are then moved from index 1 to index 2. The new (current) sum becomes 7 + 4 = 11, less than 12. So the front legs move from index 3 to index 4. The new sum becomes, 7 + 4 + 1 = 12; objective attained. Hurray! Even if there is another sub-array ahead, with sum equals to 12, it is the first sub-array that is considered. With this first sub-array, the variable, front holds index 4 and the variable, back holds index 2. The indexes are 2, 3 and 4 (inclusive), making the length (size) of the caterpillar three.

Note that it is possible with other problems, for the caterpillar to crawl through the array completely, and never attain the objective. 

Another way of expressing the caterpillar algorithm is:

- move the front legs, if the status is on one side of the criterion;

- move the back legs if the status is on the other side of the criterion.

- Keep repeating either of the above steps until the objective is attained.

Coding the Above Problem in JavaScript

There has to be a variable, front and a variable, back, both of which are initialized to 0 (both pairs of legs start at 0). n is the number of elements in the array. Iteration has to take place from 0 to n, though it may not reach n, because the only sub-array or first sub-array might have been found. There is a compound if-statement that checks if the total (sum) is 12, or if the total is less than 12 or if the total is greater than 12. 

If the total is less than 12, the block of the corresponding else-if construct, adds 1 to the front variable, and also adds the new front element to the running total. If the total is greater than 12, the other block of the corresponding else-if construct, adds 1 to the back variable, and subtracts the back element from the running total. The if-part of the if-compound statement checks if the total is equal to 12. If it is, it breaks the while-loop and returns true (the return statement does not need the break statement in order to break and return). The function below returns true if a sub-array with a sum equals to 12 is found, otherwise on completion of the iterations, it returns false. The program is (read through the code and comments):

<script type='text/javascript'>
    "use strict";  

    function caterpillarMethod(A, n, s) {
        let front = 0;
        let back = 0;
        let total = 0;
        let result = false;

        while (front < n) {
            if (total == s) {       
                return true;    //this breaks the while-loop as well
            }
            else if (total < s) {
                total = total + A[front];
                front = front + 1;    //the next front (not the current) for next loop (next iteration)
            }
            else if (total > s) {
                total = total - A[back];
                back = back + 1; 
            } 
        }

        return result;
    }

    const arr = [6, 2, 7, 4, 1, 3, 6];
    let ret = caterpillarMethod(arr, 7, 12);
    document.write('result: ' + ret + '<br>'); 
        
</script>

The output is: 

    result: true

Time Complexity for Caterpillar Method

The front and back variables are increased above in different passes through the body of the while loop. There is no re-scanning of the testing sub-arrays. And so the time complexity is O(n) and not O(n²). It should be better quoted as O(n+n) or precisely, O(n+n-2). 

Exercise

Problem: You are given n sticks (of lengths 1 ≤ a⁰ ≤ a¹ ≤ . . . ≤ aⁿ⁻¹ ≤ 10⁹ ). The goal is

to count the number of triangles that can be constructed using these sticks. More precisely,

we have to count the number of triplets at indices x < y < z, such that a_x + a_y > a_z.

Note: A property for all triangles is, that the sum of any 2 sides, X and Y, is always greater than the third side Z. Also, if the sum of the shorter two sides is greater than the third side, then a triangle is definitely formed. 

The third task, CountTriangles among the four tests for this lesson, has the O(n²) solution for this problem.

Conclusion

The caterpillar algorithm can be expressed as follows: 

- move the front legs, if the status is on one side of the criterion;

- move the back legs if the status is on the other side of the criterion.

- Keep repeating either of the above steps until the objective is attained.

So far as operations of only addition is concerned, the maximum slice problem algorithm (Kadane’s method), is not the same as the caterpillar algorithm. The two different kinds of algorithm are for solving different kinds of problems.