219. Contains Duplicate II

Problem

  • 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

Thought Process

  • a nested loop, to see if two distinct ele are equal and abs(j-i) <= k

White Board

Below is the white board:

Code

class Solution:
    def con_dup(self, nums, k):
        for i in range(len(nums)):
            for j in range(len(nums)):
                if i != j and (nums[i] == nums[j]) and abs(j - i) <= k:
                    return True
        return False

def test():
    #nums = [1,2,3,1]
    #k = 3

    #nums = [1,0,1,1]
    #k = 1

    nums = [1,2,3,1,2,3]
    k = 2

    cd = Solution().con_dup(nums, k)
    print(cd)

test()    

False

Complexity

  • time complexity is O(n**2), and most likely it will TLE
  • Space complexity is O(n), as I created both a dict to store results

Optimization

The brute force solution will have TLE problem on Leetcode. There's a solution that I can combine a ht and shifting window.

    Have two pointers, l and l+k For a given state:
  • if nums[l:l+k] has dup values, then return true, as within nums[l: l+k], the max distance between two dup values is k
  • if nums[l:l+k] doesn't have dup values,
  • move l to the right, l+=1;
  • check if nums[l+k+1] exists in nums[l+1:l+k]
  • * if exists, return true * if not, l+k += 1 * keep looping until l < len(nums)
class Solution2:
    def create_ht(self, nums, ht):
        for num in nums:
            if num not in ht:
                ht[num] = 1
            else:
                ht[num] += 1
        return ht

    def con_dup2(self, nums, k):
        l = 0
        r = l + k
        while l < len(nums):
            ht = self.create_ht(nums[l:l+k+1], {})            
            #print(ht)
            for val in ht.values():
                if val > 1:
                    # if dups exist in nums[l:l+k]
                    return True                
            if (l+k+1 < len(nums)) and (nums[l+k+1] in nums[l+1:l+k]):
                return True
            l += 1
        return False

def test():
    nums = [1,2,3,1]
    k = 3
    cd = Solution2().con_dup2(nums, k)
    print(cd)

test()    
#+end_src

#+RESULTS:
#+begin_src org
True
#+end_src

Above solution still TLE.

Another way to think is rather have a dict, use set. Apply set on the list, if len(set) < len(list), that means there muse be duplicate

#+BEGIN_SRC ipython :session :exports both :results output org
class Solution3:
    def con_dup3(self, nums, k):

        l = 0
        nums_s = set(nums[l:l+k+1])

        if k >= len(nums)-1:
            if len(set(nums)) < len(nums):
                return True

        while l+k+1 < len(nums):
            if len(nums_s) < len(nums[l:l+k+1]):
                return True
            nums_s.remove(nums[l])
            if nums[l+k+1] in nums_s:
                return True
            else:
                l += 1
                nums_s.add(nums[l+k])
        return False


def test():
    nums = [1,2,3,1]
    k = 3
    cd = Solution3().con_dup3(nums, k)
    print(cd)

test()    

True