Contains Duplicate II
Problem Description
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
Constraints:
- 1 <= nums.length <= 105
- -109 <= nums[i] <= 109
- 0 <= k <= 105
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The simplest approach to solve this problem is to check every pair of elements in the array. If two elements are the same and are within the given range k from each other, we return true. Otherwise, we continue checking all possible pairs.
Code:
- Time Complexity: O(n * k): This approach involves checking all possible pairs in the array where
nis the length of the array. - Space Complexity: O(1): We are only using a constant amount of extra space.
2. Sliding Window with HashSet
Intuition:
Instead of checking each pair, we can use a sliding window of size k and a HashSet to track the elements within that window. As we slide the window through the array, we can keep checking if the current element already exists in the HashSet. If it does, it means we found a duplicate within the given range.
Code:
- Time Complexity: O(n): We iterate through the list once, each operation (add, remove, contains) of HashSet takes O(1) on average.
- Space Complexity: O(min(n, k)): The space used by the HashSet scales with the size of
k, as it only keeps track ofkelements at a time.
3. Sliding Window with HashMap
Intuition:
A small optimization can be done over the HashSet approach by using a HashMap which stores the indices. By keeping track of indices, we can avoid unnecessary otherwise possible duplicates removal. This approach reduces operations to a bare minimum required for ensuring unique elements within the window.
Code:
- Time Complexity: O(n): We traverse the array once, each operation with HashMap is O(1) on average.
- Space Complexity: O(n): In the worst case, all elements might be unique in the array. Hence, the HashMap can store up to
nunique elements and their last seen indices.