Duplicate elements within k distance from each other in Python
By Sri Vikas PrathanapuIn this tutorial, we will learn how to check if a given array contains duplicate elements within k distance from each other in Python. In a given unsorted array with a given value of k.
Examples:
l = [1, 2, 3, 1, 2, 3, 4], k = 2
Output: NO
l= [1, 2, 3, 1, 4, 5],k=3
Output: YES
My Approach:
In this, we are going to run a loop where for each iteration we will make a sub-list of k contagious elements of the given list. Our loop run in the range of (n-k+1) where n is the length of the list. (n-k+1) because every list has exactly (n-k+1) contagious subsets. Then duplications are removed from the sub list saving it in another empty sublist. Then the length of those subsets is compared. If any duplicate is present within k distance then we will print “YES” if not present “NO”.
Python program: Duplicate elements within k distance from each other
Steps to Write program:
- Take the unsorted array as input.
- Store length of the array in variable and store value of distance in which duplication is not allowed in k.
- Then we will make contagious sublists with k elements.
- For each sublist, we will compare its length with the length of the sublist in which duplicates are removed.
- In the first case where lengths are equal then it confirms given array doesn’t contain duplicate elements within k distance and we print “NO”.
- In another case where lengths are not equal then it confirms that array has duplicates elements within k distance and we print “YES”.
arr=[1, 8, 1, 2, 3, 4]
n=len(arr)
k=3
s=0
for i in range(n-k+1):#loop for making subsets
l=arr[i:i+k:]#subset of length k
p=list(set(l))#removing dupilcates
if(len(p)!=len(l)):#comparing subsets
s=1
break
if(s==0):
print("NO")
else:
print("YES")
OUTPUT: YES
If there is any error or mistake in code please comment below.
You may also read:
Leave a Reply