How do you solve Contains Duplicate II on LeetCode?

Contains Duplicate II (LeetCode #219) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a HashMap allows for quick lookups and updates, which significantly reduces the time complexity.

What is the brute force solution for Contains Duplicate II?

The brute force approach for Contains Duplicate II is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach checks every possible pair of indices in the array to see if they contain the same value and are within the specified distance. This is straightforward but inefficient for large arrays. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Contains Duplicate II?

Contains Duplicate II uses the following concepts: Array, Hash Table, Sliding Window. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Contains Duplicate II?

Always clarify the problem constraints and edge cases before jumping to a solution. Think about the time and space complexity of your approach and be ready to discuss it. Practice explaining your thought process clearly as you code, as communication is key in interviews.

What are common mistakes when solving Contains Duplicate II?

Not considering the case where k = 0, which means we need to find the same element at the same index. Failing to update the index in the HashMap correctly.

#219

Contains Duplicate II

Easy

ArrayHash TableSliding WindowHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Using a HashMap allows us to keep track of the indices of elements as we iterate through the array. This way, we can quickly check if we've seen the same element within the required index distance.

⚙️

Algorithm

5 steps

1Step 1: Initialize a HashMap to store the last index of each element.
2Step 2: Loop through the array with index i.
3Step 3: For each element, check if it exists in the HashMap. If it does, check the difference between the current index and the stored index.
4Step 4: If the difference is less than or equal to k, return true. Update the HashMap with the current index for that element.
5Step 5: If no such pair is found after checking all elements, return false.

solution.py7 lines

1def containsNearbyDuplicate(nums, k):
2    index_map = {}
3    for i, num in enumerate(nums):
4        if num in index_map and i - index_map[num] <= k:
5            return True
6        index_map[num] = i
7    return False

ℹ

Complexity note: The time complexity is O(n) because we only loop through the array once. The space complexity is O(n) due to the HashMap storing indices.

1Using a HashMap allows for quick lookups and updates, which significantly reduces the time complexity.
2Understanding the problem constraints helps in choosing the right data structure.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.