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: trueExample 2:
Input: nums = [1,0,1,1], k = 1
Output: trueExample 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) —
loading...
Last Post: Teaching Kids Programming - Uniform Cost Search Algorithm to Solve Single-Source Shortest Path in a Graph
Next Post: Teaching Kids Programming - Introduction to Two Players Zero-Sum Game (Number Halving)