Teaching Kids Programming – Duplicate Numbers of Max Distance in Array (Sliding Window/Two Pointer Algorithms)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i – j) <= 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

Bruteforce Algorithm: Duplicate Numbers of Max Distance

If the number of numbers (n) is small, we can bruteforce all pairs of indices.

1
2
3
4
5
6
7
8

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        for i in range(n):
            for j in range(i):
                if nums[i] == nums[j] and i - j <= k:
                    return True
        return False

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        for i in range(n):
            for j in range(i):
                if nums[i] == nums[j] and i - j <= k:
                    return True
        return False

Time complexity is O(N^2) and the space complexity is O(1) constant.

Using Hash Table to Remember the Index of Last Occurrence

We can use a hash table aka dictionary to remember the last index of a number, and then we can look it up and check the distance to last if it appears prior to this:

1
2
3
4
5
6
7
8

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        data = {}
        for i, j in enumerate(nums):
            if j in data and i - data[j] <= k:
                return True
            data[j] = i
        return False

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        data = {}
        for i, j in enumerate(nums):
            if j in data and i - data[j] <= k:
                return True
            data[j] = i
        return False

Time and space complexity is O(N).

Duplicate Numbers of Max Distance in Array via Sliding Window / Two Pointer Algorithm

We can store all numbers within K distance in a hash set. As we move along to the right, the sliding window (size K) also moves. We update the sliding window by removing the leftmost element at each round, and we can directly check if the current number is in the sliding window as it should be less or equal than K to all numbers in the sliding window.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        data = set()
        for i, j in enumerate(nums):
            if i > k:
                data.remove(nums[i - k - 1])
            if j in data:
                return True
            data.add(j)
        return False

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        data = set()
        for i, j in enumerate(nums):
            if i > k:
                data.remove(nums[i - k - 1])
            if j in data:
                return True
            data.add(j)
        return False

Time and space complexity is also O(N).

–EOF (The Ultimate Computing & Technology Blog) —