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