Duplicate elements within k distance from each other in Python

In 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:

  1. Take the unsorted array as input.
  2. Store length of the array in variable and store value of distance in which duplication is not allowed in k.
  3. Then we will make contagious sublists with k elements.
  4. For each sublist, we will compare its length with the length of the sublist in which duplicates are removed.
  5. 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”.
  6. 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