Codility - Lesson 15 Caterpillar Method - 3. CountDistinctSlices

Source Link:

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

Question:

An integer M and a non-empty zero-indexed 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:

class Solution { public int solution(int M, int[] A); }

that, given an integer M and a non-empty zero-indexed 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.

Assume that:

• 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].

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(M), beyond input storage (not counting the storage required for input arguments).

My Solution: 

Notes:

1. // main idea: use "boolean[]" to record if an integer is already seen, also use "leftEnd" and "rightEnd"

boolean[] seen = new boolean[M+1]; // from 0 to M
2. // key point: move the "leftEnd" and "rightEnd" of a slice
while(leftEnd < A.length && rightEnd < A.length){
...
}

3. // case 1: distinct (rightEnd)

4. // case 2: not distinct

5. 
return numSlice;

Codility - Lesson 15 Caterpillar Method - 2. CountTriangles

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

Question:

A zero-indexed array A consisting of N integers is given. A triplet (P, Q, R) is triangular if it is possible to build a triangle with sides of lengths A[P], A[Q] and A[R]. In other words, triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:

• A[P] + A[Q] > A[R],
• A[Q] + A[R] > A[P],
• A[R] + A[P] > A[Q].

For example, consider array A such that:

A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 12

There are four triangular triplets that can be constructed from elements of this array, namely (0, 2, 4), (0, 2, 5), (0, 4, 5), and (2, 4, 5).

Write a function:

class Solution { public int solution(int[] A); }

that, given a zero-indexed array A consisting of N integers, returns the number of triangular triplets in this array.

For example, given array A such that:

A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 12

the function should return 4, as explained above.

Assume that:

• N is an integer within the range [0..1,000];
• each element of array A is an integer within the range [1..1,000,000,000].

Complexity:

• expected worst-case time complexity is O(N2);
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

My Solution:
Notes:
1. // important: sort the edges, so that we just need to check if "1st edge + 2nd edge > 3rd edge"
Arrays.sort(A);
2. // Using "Caterpillar method", so we can have O(n^2), not O(n^3)
// key point of "Caterpillar method"
if(rightEnd < A.length && A[i] + A[leftEnd] > A[rightEnd]){
rightEnd++; // increase the Caterpillar
}
else{
numTriangle = numTriangle + (rightEnd - leftEnd - 1);
leftEnd++; // decrease the Caterpillar
}
3.
return numTriangle;

Codility - Lesson 15 Caterpillar Method - 1. AbsDistinct

Source Link:

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

Question:

A non-empty zero-indexed array A consisting of N numbers is given. The array is sorted in non-decreasing order. The absolute distinct count of this array is the number of distinct absolute values among the elements of the array.

For example, consider array A such that:

A[0] = -5 A[1] = -3 A[2] = -1 A[3] = 0 A[4] = 3 A[5] = 6

The absolute distinct count of this array is 5, because there are 5 distinct absolute values among the elements of this array, namely 0, 1, 3, 5 and 6.

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty zero-indexed array A consisting of N numbers, returns absolute distinct count of array A.

For example, given array A such that:

A[0] = -5 A[1] = -3 A[2] = -1 A[3] = 0 A[4] = 3 A[5] = 6

the function should return 5, as explained above.

Assume that:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [−2,147,483,648..2,147,483,647];
• array A is sorted in non-decreasing order.

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

My Solution:

Notes:

1. // using "Set"
Set<Integer> set = new HashSet<>();

2. // note: using "Math.abs(int)"
if( set.contains( Math.abs(A[i]) ) == false ){
set.add( Math.abs(A[i]) );
}

3. 
return set.size();

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.