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

68
October 13, 2019, at 7:10 PM

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 
Answer 1

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
READ ALSO
Problems with CORS and JSON

Problems with CORS and JSON

I habe a client written in Javascript (react) which runs on localhost:3000 Here I have a button that sends the credentials to my backend written in python and using flaskThe endpoint is running on localhost:5000/login

62
Multiple DELETE requests crash server

Multiple DELETE requests crash server

I use this fake json-server api

58
Ajax request not working on button click using PHP and MySQL

Ajax request not working on button click using PHP and MySQL

I'm sending an ajax request through JavaScript on clicking a buttonWhen button gets clicked a function is called from where ajax request is performed

72
getRandomInt always returns 0

getRandomInt always returns 0

I am using the function from developermozilla

104