Count Subarray in Which Every Elements Appears At Least Twice
146

I met this question in a simulation test. I have an O(n^2) solution but reveive time limit exceed error. What would be a better solution?

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]

My solution(time limit exceeded):

import collections
def subarray_with_notUnique_element(arr):
    ans=0
    for i in range(len(arr)):
        d=collections.defaultdict(int)
        count=0
        for j in range(i,len(arr)):
            d[arr[j]]+=1
			#if an element is unique
            if d[arr[j]]==1:
                count+=1
            elif d[arr[j]]==2:
                count-=1
            #if no element is unqie, increase ans
			if count==0:
                ans+=1
    return ans

How to make it faster?

Comments (0)