Contains Duplicate II

2 min read
Array
LC-Easy
Sliding Window

Oct 21, 2022

3 years ago

LeetCode

Solution

Sliding window of size k where we keep a set which has all characters in current window
As left boundary moves forward, remember to delete from set
If valid sliding window of required length in seen, immediately return true

Time	Space	Explanation
`O(n)`	`O(k)`

function containsNearbyDuplicate(nums: number[], k: number): boolean { let l = 0; const seen = new Set(); for(let r = 0; r < nums.length; r++) { if (r - l > k) { seen.delete(nums[l++]); } if (seen.has(nums[r])) { return true; } seen.add(nums[r]); } return false; };

O(n) space solution

Just keep track of index of all number seen previously
If there's a duplicate number and the difference in index is <= k, return true
ELSE, update the index to current number, because there might be another duplicate ahead that fulfills the condition that the difference in indexes needs to be <= k
Only worse than O(k) solution because of extra space- TC is the same

function containsNearbyDuplicate(nums: number[], k: number): boolean { const seen = {} for(let i = 0; i < nums.length; i++) { if (nums[i] in seen && (i - seen[nums[i]]) <= k) { return true; } seen[nums[i]] = i; } return false; };