Practice/Meta/Leetcode 219. Contains Duplicate II

Leetcode 219. Contains Duplicate II

CodingMust

Problem

You are given an integer array nums and an integer k. Your task is to determine whether there exist two distinct indices i and j in the array such that:

1. nums[i] equals nums[j]
2. The absolute difference between i and j is at most k

In other words, find if any duplicate value appears within a window of k positions from its first occurrence.

Return true if such a pair exists, otherwise return false.

Requirements

1. Check if any two equal elements exist in the array
2. The indices of these equal elements must differ by at most k
3. Return a boolean indicating whether such a pair exists
4. Handle arrays of varying sizes efficiently

Constraints

• 1 ≤ nums.length ≤ 100,000
• -1,000,000,000 ≤ nums[i] ≤ 1,000,000,000
• 0 ≤ k ≤ 100,000
• Your solution should run in O(n) time complexity
• Aim for O(min(n, k)) space complexity

Examples

Example 1:

Input: nums = [1, 2, 3, 1], k = 3 Output: true Explanation: The number 1 appears at index 0 and index 3. The difference is |3 - 0| = 3, which is equal to k.

Example 2:

Input: nums = [1, 2, 3, 1, 2, 3], k = 2 Output: false Explanation: Although 1 appears twice at indices 0 and 3, the distance is 3 which exceeds k = 2. The same applies to 2 and 3.

Example 3:

Input: nums = [1, 0, 1, 1], k = 1 Output: true Explanation: The number 1 appears at indices 2 and 3, with a distance of 1, which satisfies k = 1.