0

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

Here's my code:

class Solution(object):
def containsNearbyDuplicate(self, nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: bool
    """
    def helper(lnums, n):
        if len(lnums) == 0 and n == 0:
            return False
        elif len(lnums) > n:
            for i in lnums[1:n]:
                if i == lnums[0]:
                    return True
            lnums.pop(0)
            return helper(lnums, n)
        else:
            return False

    return helper(nums, k)

Can anyone point out why I'm doing this wrong??? I know there's something wrong in the elif. But I have no idea why this doesn't work.

user2390182
  • 72,016
  • 6
  • 67
  • 89
Wei Bovey
  • 33
  • 1
  • 5

1 Answers1

0

Some little tweaks to make it work:

def helper(lnums, n):
    if len(lnums) == 0 or n == 0:  # note: or, not and
        return False
    else:   # there do NOT have to be at least n elements, why would there?
        for i in lnums[1:n+1]:  # exclusive upper slice boundary -> n+1
            if i == lnums[0]:
                return True
        lnums.pop(0)
        return helper(lnums, n)

Or without expensive popping and recursion, using some fine utils like any and enumerate:

def helper(lnums, n):
    return any(x in lnums[i+1:i+1+n] for i, x in enumerate(lnums))
user2390182
  • 72,016
  • 6
  • 67
  • 89
  • What if lnums has 2 objects, however n = 3, then lnums[1:n+1] will be out of range??? I didn't get why it works. – Wei Bovey Oct 25 '18 at 13:37
  • There is no out of bounds with Python slices: see e.g. https://stackoverflow.com/questions/22951107/why-pythons-list-slicing-doesnt-produce-index-out-of-bound-error. And still `nums=[1,1], k=3` should return `True`, so these lengths have to be considered. – user2390182 Oct 25 '18 at 13:39