Codility - Lesson 15 Caterpillar Method

Source Link: 
https://app.codility.com/programmers/lessons/15-caterpillar_method/

Some Notes:
The Caterpillar method is a likeable name for a popular means of solving algorithmic tasks.  We remember the front and back positions of the caterpillar, and at every step either of them is moved forward.

15.1. Usage example
For example, in the following sequence we are looking for a subsequence whose total equals s = 12.



Let’s initially set the caterpillar on the first element. Next we will perform the following steps: 

• if we can, we move the right end (front) forward and increase the size of the caterpillar;

• otherwise, we move the left end (back) forward and decrease the size of the caterpillar.

In this way, for every position of the left end we know the longest caterpillar that covers elements whose total is not greater than s. If there is a subsequence whose total of elements equals s, then there certainly is a moment when the caterpillar covers all its elements.

15.1: Caterpillar in O(n) time complexity. 
1 def caterpillarMethod(A, s): 
2 n = len(A) 
3 front, total = 0, 0 
4 for back in xrange(n): 
5 while (front < n and total + A[front] <= s): 
6 total += A[front] 
7 front += 1 
8 if total == s: 
9 return True 
10 total -= A[back] 
11 return False

Notice that at every step we move the front or the back of the caterpillar, and their positions will never exceed n. Thus we actually get an O(n) solution.