Problem

An integer M and a non-empty array A consisting of N non-negative integers are given. All integers in array A are less than or equal to M. 

A pair of integers (P, Q), such that 0 <= P <= Q < N, is called a slice of array A. The slice consists of the elements A[P], A[P + 1], ..., A[Q]. A distinct slice is a slice consisting of only unique numbers. That is, no individual number occurs more than once in the slice.

For example, consider integer M = 6 and array A such that: 

    A[0] = 3

    A[1] = 4

    A[2] = 5

    A[3] = 5

    A[4] = 2

There are exactly nine distinct slices: (0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2), (3, 3), (3, 4) and (4, 4). 

The goal is to calculate the number of distinct slices.

Write a function: 

    function solution(M, A);

that, given an integer M and a non-empty array A consisting of N integers, returns the number of distinct slices. 

If the number of distinct slices is greater than 1,000,000,000, the function should return 1,000,000,000.

For example, given integer M = 6 and array A such that: 

    A[0] = 3

    A[1] = 4

    A[2] = 5

    A[3] = 5

    A[4] = 2

the function should return 9, as explained above. 

Write an efficient algorithm for the following assumptions:

·         N is an integer within the range [1..100,000];

·         M is an integer within the range [0..100,000];

·         each element of array A is an integer within the range [0..M].

Note:

0 is a non-negative number here. 

A slice of values such as {4, 5, 5} is invalid, because 5 occurs more than once.

Another slice like {2, 5, 3, 4, 5, 7, 5, 8} is also invalid because 5 still occurs more than once (three times in three different places). 

This lesson is on caterpillar method, so it should occur to the reader, that caterpillar method is needed to solve the problem.

Illustration

The caterpillar method will be used for illustration with the following list: 

List: 3, 4, 5, 5, 2

The table is:

At the beginning, the front and back variables are at index 0. They both point to 3. That is one slice, {3} for index (0,0). The front variable (legs) moves one place ahead. The second slice {3,4} for (0,1) is obtained. The front variable next moves one place ahead. The third slice {3,4,5} for (0,2) is obtained. The front variable next attempts to move one place ahead but meets 5, which repeats at index 3, and the variable does not move to that position. This means that all the previous numbers should have been memorized. 

Since the front variable cannot move further, instead the back variable moves one place ahead to index 1. The front variable then jumps backwards to index 1 from index 2. This results in a new slice, the fourth slice {4} for (1,1). The front variable next moves to index 2. The fifth slice {4,5} for (1,2) is obtained. The front variable next attempts to move one place ahead but meets 5, which repeats at index 3, and does not move to that position. This means that all the previous numbers in the previous sequence should have been memorized.

Since the front variable cannot move further, instead the back variable moves one place ahead to index 2. The front variable then jumps backwards to index 2 from index 2 (no change really). This results in a new slice, the sixth slice {5} for (2,2). The front variable next attempts to move one place ahead but meets 5, which repeats at index 3, and does not move to that position. This means that all the previous numbers in the previous sequence should have been memorized. This point is at the end of the previous sequence, with one element in a slice. 

After ending the sequence that is reducing in length and ends at one element slice, both the front and back variables have to move to the next index, 3. From there, the algorithm restarts as if it were starting from the beginning at index 0. They both now point to the second 5 at index 3. That is one slice, {5} for index (3,3). It is the seventh slice. Now there are two slices {5} and {5} at indexes 2 and 3 respectively. Note that these are two different distinct slices in the sense that they belong to two different indexes.

The front variable next moves one place ahead. The eighth slice {5,2} for (3,4) is obtained. The front variable next attempts to move one place ahead but meets the end of the list, and cannot move further anymore. This means that all the previous numbers in the last sequence should have been memorized. 

Since the front variable cannot move further, instead the back variable moves one place ahead to index 4. The front variable then jumps backwards to index 4 from index 4 (no change really). This results in a new slice, the ninth slice {2} for (4,4). The algorithm should end at this point.

Memorization

Memorization is done with an accumulator. Before the algorithm begins, the accumulator is (initialized):

 The front, back and counter variables are initialized as follows:

    int front=0;  // for caterpillar

    int back=0;  // for caterpillar

    int count=0; 

When the algorithm ends, the accumulator is:

 To see how this table (final state of accumulator) was arrived at, the reader has to substitute all the given values (given array) into the algorithm.

The new values for the counter variable, in order, are: 

    1, 3, 6, 7, 9

Efficient Program

The following program does not strictly follow the above illustrative algorithm. However, they are fundamentally the same.

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

function solution(M, A) {
    let N = A.length;
    let count = 0;
    const acc = new Array(M+1).fill(-1);    //acc = {-1, -1, -1, -1, -1, -1, -1}
    
    let front=0;  // for caterpillar
    let back=0;  // for caterpillar
    
    while(front<N){
        if (acc[A[front]]>=back){    //identifies repetition if A[i] addressed before in sub-sequence
            back=acc[A[front]]+1;
        }else {
            acc[A[front]]=front;
            count = count + (front - back + 1);
            if (count>1000000000)
                return 1000000000;
            front++;
        }
    }  

    return count;
}

    const A = [3, 4, 5, 5, 2];
    let ret = solution(6, A);
    document.write(ret + '<br>');

</script>

    Task score : 100% -  Correctness : 100% ; Performance : 100%

    Detected time complexity : O(N) 

The reader should substitute all the given values (given array) into the algorithm, to see how the final state of the accumulator and the counter numbers were arrived at. Note in particular, what happened at the repetition. Do that in order to gain more confidence.

Thanks for reading.