count distinct slices in an array

Question

I was trying to solve this problem.

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.

Thanks in advance.

#include <algorithm>
#include <cstring>
#include <cmath>
#define MAX 100002

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

using namespace std;

bool check[MAX];

int solution(int M, vector<int> &A) {
    memset(check, false, sizeof(check));
    int base = 0;
    int fibot = 0;
    int sum = 0;

    while(fibot < A.size()){

        if(check[A[fibot]]){
            base = fibot;
        }

        check[A[fibot]] = true;

   sum += fibot - base + 1;
        fibot += 1;  
    }

    return min(sum, 1000000000);
}

Bettor

Answer 1

The solution is not correct because your algorithm is wrong.

First of all, let me show you a counter example. Let A = {2, 1, 2}. The first iteration: base = 0, fibot = 0, sum += 1. That's right. The second one: base = 0, fibot = 1, sum += 2. That's correct, too. The last step: fibot = 2, check[A[fibot]] is true, thus, base = 2. But it should be 1. So your code returns1 + 2 + 1 = 4 while the right answer 1 + 2 + 2 = 5.

The right way to do it could be like this: start with L = 0. For each R from 0 to n - 1, keep moving the L to the right until the subarray contais only distinct values (you can maintain the number of occurrences of each value in an array and use the fact that A[R] is the only element that can occur more than once).

There is one more issue with your code: the sum variable may overflow if int is 32-bit type on the testing platform (for instance, if all elements of A are distinct).

As for the question WHY your algorithm is incorrect, I have no idea why it should be correct in the first place. Can you prove it? The base = fibot assignment looks quite arbitrary to me.

Versicle

I understand enough. Thank you very much. – Bettor

Answer 2

I would like to share the explanation of the algorithm that I have implemented in C++ followed by the actual implementation.

1. Notice that the minimum amount of distinct slices is N because each element is a distinct one-item slice.
2. Start the back index from the first element.
3. Start the front index from the first element.
4. Advance the front until we find a duplicate in the sequence.
5. In each iteration, increment the counter with the necessary amount, this is the difference between front and back.
6. If we reach the maximum counts at any iteration, just return immediately for slight optimisation.
7. In each iteration of the sequence, record the elements that have occurred.
8. Once we have found a duplicate, advance the back index one ahead of the duplicate.
9. While we advance the back index, clear all the occurred elements since we start a new slice beyond those elements.

The runtime complexity of this solution is O(N) since we go through each
element.

The space complexity of this solution is O(M) because we have a hash to store the occurred elements in the sequences. The maximum element of this hash is M.

int solution(int M, vector<int> &A)                                             
{                                                                               
  int N = A.size();                                                             
  int distinct_slices = N;                                                      
  vector<bool> seq_hash(M + 1, false);                                          
  for (int back = 0, front = 0; front < N; ++back) {                            
    while (front < N and !seq_hash[A[front]]) { distinct_slices += front - back; if (distinct_slices > 1000000000) return 1000000000; seq_hash[A[front++]] = true; }
    while (front < N and back < N and A[back] != A[front]) seq_hash[A[back++]] = false;
    seq_hash[A[back]] = false;                                                  
  }                                                                             
                                                                                
  return distinct_slices;                                                       
}

Disband

Answer 3

100% python solution that helped me, thanks to https://www.martinkysel.com/codility-countdistinctslices-solution/

def solution(M, A):
    
        the_sum = 0
    
        front = back = 0
    
        seen = [False] * (M+1)
    
        while (front < len(A) and back < len(A)):
    
            while (front < len(A) and seen[A[front]] != True):
    
                the_sum += (front-back+1)
    
                seen[A[front]] = True
    
                front += 1
    
            else:
    
                while front < len(A) and back < len(A) and A[back] != A[front]:
    
                    seen[A[back]] = False
    
                    back += 1
    
                seen[A[back]] = False
    
                back += 1
                   
        return min(the_sum, 1000000000)  
           

Schoonmaker

Answer 4

Solution with 100% using Ruby

LIMIT = 1_000_000_000

def solution(_m, a)
  a.each_with_index.inject([0, {}]) do |(result, slice), (back, i)|
    return LIMIT if result >= LIMIT
    slice[back] = true
    a[(i + slice.size)..-1].each do |front|
      break if slice[front]
      slice[front] = true
    end
    slice.delete back
    [result + slice.size, slice]
  end.first + a.size
end

Breeches

No explanation, just random code, is rarely the best for education purposes. – Tier

Answer 5

Using Caterpillar algorithm and the formula that S(n+1) = S(n) + n + 1 where S(n) is count of slices for n-element array java solution could be:

 public int solution(int top, int[] numbers) {
        int len = numbers.length;
        long count = 0;

        if (len == 1) return 1;

        int front = 0;
        int[] counter = new int[top + 1];

        for (int i = 0; i < len; i++) {
            while(front < len && counter[numbers[front]] == 0 ) {
                count += front - i + 1;
                counter[numbers[front++]] = 1;
            }

            while(front < len && numbers[i] != numbers[front] && i < front) {
                counter[numbers[i++]] = 0;
            }

            counter[numbers[i]] = 0;

            if (count > 1_000_000_000) {
                return 1_000_000_000;
            }
        }

        return count;
    }

Romie