You are given an array consisting of elements in the form A1, A2, A3…….An. The task is to find whether the array can be formed as a Contiguous Distinct Sub Array or Not. You need to find whether the array can be converted to contiguous sub-arrays that consist of similar elements and there are a distinct number of each element.
The elements once encountered should not appear later in the array as it would not be contiguous
Example:
Input:[ 1 1 3 6 6 6 ]
Output: YES
Explanation:
The given elements of the can be converted to Contiguous Distinct Set Array in the form of [1, 1] [3] [6, 6, 6]and also
no. of 1’s = 2
no. of 3’s = 1
no. of 6’s = 3
which are distinctInput:[ 1 1 3 5 2 2 2 3 ]
Output: NO
Explanation:
The given elements of the cannot be converted to Contiguous Distinct Set Array as sub array [3 5 2 2 2 3]
violates the condition(elements need to be contiguous) 3 again appears after 5 and 2.Input:[9 9 4 4 4 1 6 6]
Output: NO
Explanation:
The given elements of the cannot be converted to Contiguous Distinct Set Array
It is of the form [9, 9] [4, 4, 4] [1] [6, 6] So the elements are present contiguous
But the no. of 9’s=2 which is also equal to the no. of 6’s=2
Hence the no.s of different elements of the array are not Distinct
hence the Answer is NO
Solution:
Python3
from collections import Counter# function to check contiguous # distinct set arraydef contig_distinct_setarr(l, n): c = Counter(l) a = list(set(l)) b =[] flag = True for j in c.values(): # iterating and moving it to another # array if already present we print NO # when it finds no. of different elements # to be equal if no. of x's = no. of y's # So we break of the loop if j not in b: b.append(j) else: print("NO") flag = False break # If already there are similar elements # in c.values()- the count of elements # flag = False and we dont need to check # the below condition If not flag = False # then the iterate through the array loop if (flag != False): i, k = 0, 0 # for each elements in set a # cou stores the count of a[i] while k<len(a): cou = c[a[i]] x = l.index(a[i]) # here we extract thecontiguous # sub array of length equal to # the count of the element temp =(l[x:x + cou]) # if the number of elements of # subsequences is not equal to # the value of element in the # dictionary print NO if len(temp) != c[a[i]]: print("NO") flag = False break k+= 1 i+= 1 # if we have iterated all over the array # and the condition is satisfied we print # YES if flag == True: print("YES")# initialize the array and its lengthn = 6l =[1, 1, 3, 6, 6, 6]contig_distinct_setarr(l, n) |
Output:
YES
Another approach without using any module –
In this approach, we will not use any external module like collections. We will simply use a dictionary to store the occurrence of each element along with the element. The elements will work as the key of the dictionary and its respective occurrences will act as the value. Then we will use a variable to store all the values in a list format, then convert the list into a set and compare their lengths. Now if the length is the same it means none of the elements have the same number of occurrences in the given list.
Example –
Input:[ 1 1 3 6 6 6 ]
Output: YES
Explanation:We will first initialize a blank dictionary to count the occurrence of each element and store them as key:value pair. We will iterate over the given array once and check if the element is already inside of that dictionary or not. If not then we will add it into the dictionary and make the count as 1, otherwise we will just increase the count.For this given array –
FIrst Iteration – 1 gets into the blank dictionary and the count becomes 1 i.e {1:1}
Second Iteration – 1 is already present in the dictionary so the count increases by 1 i.e {1:2}
Third Iteration – new element 3 gets inserted into the dictionary with count 1 i.e {1:2,3:1}
Fourth Iteration – new element 6 gets inserted into the dictionary with count 1 i.e {1:2,3:1,6:1}
Fifth and Sixth Iteration – The count of 6 incease once each iteration and final dictionary becomes –
{1:2,3:1,6:3}
Now if we see carefully the values of the dictionary is 2,1 and 3 which are distinct. Therefore our program returns True or YES.
Python3
# Program to check given list forms# Contiguous subarray or not# without using any external in built module# defining the function which# takes an input arr of type list# and returns a value of type booleandef count_occurrence(arr : list()) -> bool: # Initializing a blank dictionary # to store the occurrence of each element # as key value pairs dic = {} # Iterating over the array # and checking if the element is # present in the dictionary or not for i in arr: if i not in dic: dic[i]= 1 else: dic[i] += 1 # fetching only the values from # the dictionary vals = list(dic.values()) # Converting them into sets # so that if there is any duplicate it will be removed set_vals = set(vals) # Checking if the length of the set # is same as of the normal list return len(vals)==len(set_vals)# Driver Code lst_1 = [9,9,4,4,4,1,6,6]lst_2 = [1,1,3,6,6,6]# Returns Falseprint(count_occurrence(lst_1))# Returns Trueprint(count_occurrence(lst_2)) |
False True
Time Complexity – O(n), where n is the size of the list
Space Complexity – O(n), space used to create dictionary
