leetcode/src/notes/219_contains_duplicate_ii.md

Contains Duplicate II

Problem Number: 219 Difficulty: Easy Category: Array, Hash Table, Sliding Window LeetCode Link: https://leetcode.com/problems/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 <= 10^5
• 0 <= k <= 10^5
• -10^9 <= nums[i] <= 10^9

My Approach

I used a Sliding Window approach with hash set to track elements within the window. The key insight is to maintain a sliding window of size k+1 and check for duplicates within this window.

Algorithm:

1. Handle edge case: if array length ≤ 1, return False
2. Initialize hash set to track elements in current window
3. For each element:
   • If element already in set, return True (duplicate found)
   • Add element to set
   • If set size > k, remove oldest element (nums[i-k])
4. Return False if no duplicates found

Solution

The solution uses sliding window with hash set to check for duplicates within k distance. See the implementation in the solution file.

Key Points:

• Uses sliding window of size k+1
• Maintains hash set for O(1) lookup
• Removes oldest element when window exceeds k
• Returns True as soon as duplicate is found
• Handles edge cases properly

Time & Space Complexity

Time Complexity: O(n)

• Single pass through the array
• Hash set operations are O(1)
• Total: O(n)

Space Complexity: O(k)

• Hash set stores at most k+1 elements
• Total: O(k)

Key Insights

1. Sliding Window: Using sliding window of size k+1 ensures we only check elements within k distance.

2. Hash Set: Using hash set provides O(1) lookup for duplicates.

3. Window Management: Removing oldest element when window exceeds k maintains the sliding window.

4. Early Return: Return True as soon as duplicate is found within the window.

5. Distance Constraint: The k parameter limits the window size and search space.

6. Efficient Removal: Removing oldest element keeps the window size bounded.

Mistakes Made

1. Wrong Window Size: Initially might use wrong window size.

2. Complex Logic: Overcomplicating the sliding window management.

3. Wrong Removal: Not removing the correct element when window exceeds k.

4. Missing Edge Cases: Not handling arrays with length ≤ 1.

Related Problems

• Contains Duplicate (Problem 217): Check for any duplicates
• Contains Duplicate III (Problem 220): Check for duplicates within k distance and t difference
• Longest Substring Without Repeating Characters (Problem 3): Find longest unique substring
• Minimum Size Subarray Sum (Problem 209): Find minimum subarray with given sum

Alternative Approaches

1. Hash Map with Indices: Store indices in hash map - O(n) time, O(n) space
2. Brute Force: Check all pairs within k distance - O(nk) time, O(1) space
3. Sorting with Indices: Sort with indices and check adjacent - O(n log n) time, O(n) space

Common Pitfalls

1. Wrong Window Size: Using incorrect window size for sliding window.
2. Complex Logic: Overcomplicating the sliding window management.
3. Wrong Removal: Not removing the correct element when window exceeds k.
4. Missing Edge Cases: Not handling edge cases properly.
5. Inefficient Approach: Using brute force when sliding window is more efficient.

---

|

Note: This is a sliding window problem that demonstrates efficient duplicate detection within a distance constraint.