CODEWITHSUNDEEP
javaarraysalgorithm
Arefe
Arefe

Reputation: 12461

Count the number of distinct slices (containing only unique numbers)

I solved the following Codilty problem provided.

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:

class Solution { public int solution(int M, int[] 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].

My solution is here, 

public static int solution(int M, int[] A) {

        boolean[] visited = new boolean[M + 1];

        int N = A.length;


        int result = 0;

        for (int i = 0; i < N; i++) {

            int k = i;
            int count = 0;

            while (i < N && !visited[A[i]]) {

                count++;
                visited[A[i]] = true;

                i++;
            }

            i -=1;

            // 3, 4, 5, 5, 2, 5, 4
            int j = i;

            while (j >= k && visited[A[j]]) {

                visited[A[j]] = false;
                j--;
            }

            result += count * (count + 1) / 2;
        }

        return result;
    }

However, correctness and performance are low estimated by the online judge. How do I improve that?

Upvotes: 1

Views: 2954

Answers (2)

גלעד ברקן
גלעד ברקן

Reputation: 23945

I like the idea of the two pointer approach and O(1) update to the visited array that MBo clarified. Here's a single pointer idea that uses a hash set for uniqueness, which gets cleared each time a new segment starts.

function f(A){
  var sum = 0
  var set = new Set
  var len = 0
  
  for (a of A){
    if (sum >= 1000000000)
      return 1000000000
      
    if (set.has(a)){
      sum += len*(len+1)/2
      len = 1
      set.clear()
      
    } else {
      len++
      set.add(a)
    }
  }
  sum += len*(len+1)/2
  
  return Math.min(sum, 1000000000)
}

var A = [3, 4, 5, 5 ,2]

console.log(f(A))

Upvotes: 0

MBo
MBo

Reputation: 80287

Seems you have chosen right approach but made mistakes in implementation details - decrementing index in bad idea.

Make two indexes - left and right.

a) Move right until repeated element ("stopper") is met - essentially you are performing this step in the first while-loop. If you made n steps before stopping - there are n*(n-1)/2 slices.

b) Now move left index until you find the same element as "stopper" and stop after it. Current slice is good again

Repeat a) and b) till the end. Note that both indexes move only forward, and complexity is linear

Upvotes: 3

Related Questions