CODEWITHSUNDEEP
pythonpython-3.xduplicates
DeniseP123
DeniseP123

Reputation: 23

Python finding duplicates: Find out if there are duplicate numbers and the index diff is at most k

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1: Input: nums = [1,2,3,1], k = 3 Output: true

Example 2: Input: nums = [1,0,1,1], k = 1 Output: true

Example 3: Input: nums = [1,2,3,1,2,3], k = 2 Output: false

I have been looking at my code for a good 10 min and still do not understand what went wrong... My code runs, but it returns True for Example 1, False for Example 2, True for Example 3. (It should be True for Example 1, True for Example 2, and False for Example 3.

Can anyone please help me identify where the issue is in my code? A Python newbie here, thanks in advance for your help! 

def findDistinct(nums,k):   
    nums = sorted(nums)  # sort first 
    for i in range(len(nums)):
        for j in range(i+1,len(nums)):  
            if nums[i] == nums[j] and abs(j-i)<=k:
                return True
            else:
                return False

Upvotes: 1

Views: 799

Answers (1)

user2390182
user2390182

Reputation: 73470

You return False way too early. Just because you do not find a duplicate for the first index that you test does not mean you won't find a duplicate for a later index:

def findDistinct(nums, k):   
    # sorting makes no sense, you lose the information about the initial indexes
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):  
            if nums[i] == nums[j] and abs(j-i)<=k:
                return True
    return False  # now you have checked all indexes

You can shorten this to:

def findDistinct(nums, k):   
    for i, el in enumerate(nums):
        if el in nums[i+1:i+k+1]:
            return True
    return False  # now you have checked all indexes

Upvotes: 1

Related Questions