Count the number of sub arrays such that each element in the subarray appears at least twice

user_14806201 0
Viewed 2719

I have come across a problem and can't seem to come up with an efficient solution. The problem is as follows:

Given an array A, count the number of consecutive contiguous subarrays such that each element in the subarray appears at least twice.

Ex, for:

A = [0,0,0]

The answer should be 3 because we have

A[0..1] = [0,0]
A[1..2] = [0,0]
A[0..3] = [0,0,0]

Another example:

A=[1,2,1,2,3]

The answer should be 1 because we have:

A[0..3] = [1,2,1,2]

I can't seem to come up with an efficient solution for this algorithm. I have an algorithm that checks every possible subarray (O(n^2)), but I need something better. This is my naive solution:

def duplicatesOnSegment(arr):
    total = 0
    for i in range(0,len(arr)):
        unique = 0
        test = {}
        for j in range(i,len(arr)):
            k = arr[j]
            if k not in test:
                test[k] = 1
            else:
                test[k] +=  1

            if test[k] == 1:
                unique += 1
            elif test[k] == 2:
                unique -= 1
            if unique == 0:
                total += 1
    return total
complexity-theory list python
2 Answers

Your program in the worst case is greater than O(n^2) as you are using if k not in test in nested loop. This in in worst case is O(n) resulting in overall worst case O(n^3). I have this, O(n^2) in worst, solution which uses collections.defaultdict as hash to make this faster.

from collections import defaultdict

def func(A):
    result = 0
    for i in range(0,len(A)):
        counter = 0
        hash = defaultdict (int)
        for j in range (i, len(A)):
            hash[A[j]] += 1
            if hash[A[j]] == 2:
                counter += 1
            if counter != 0 and counter == len(hash):
                result += 1
    return result
user_112114300

To start with, I would consider the negation of the property of interest :

not(all(x in l appears at least twice)) = exists(x in l such that any other y in l != x)

Not sure yet that the previous reformulation of your question might help, but my intuition as a mathematician told me to try this way... Still feels like O(n^2) though...

my_list = ['b', 'b', 'a', 'd', 'd', 'c']

def remaining_list(el,list):
    assert el in list
    if el == list[-1]: return []
    else: return list[list.index(el)+1:]

def has_duplicate(el, list):
    assert el in list
    return el in remaining_list(el,list)

list(filter(lambda e:not(has_duplicate(e,my_list)),my_list))
user_94283420
Related