219. Contains Duplicate II

Problem Statement

link: LeetCode.cn LeetCode 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:

Input: nums = [1,2,3,1], k = 3 Output: true

Input: ` nums = [1,0,1,1], k = 1 **Output:** true`

Input: nums = [1,2,3,1,2,3], k = 2 Output: false

Constraints: 1 <= nums.length <= 10^5 -10^9 <= nums[i] <= 10^9 0 <= k <= 10^5

Solution Approach

The solution uses a hash table (pos) to keep track of the indices of elements as we iterate through the array. For each element, we check if it has appeared before and if the difference between the current index and the previous index is within the given k. If both conditions are met, we return True. If no such pair is found by the end of the iteration, we return False.

Algorithm

1. Hash Table for Index Tracking: Use a hash table (pos) to store the last seen index of each element in the array. This allows for quick lookup of previous indices.
2. Distance Check: For each element, if it has been seen before and the difference between the current index and its last recorded index is less than or equal to k, return True.
3. Update and Iterate: If the conditions are not met, update the hash table with the current index of the element and continue to the next element. If no valid pair is found by the end of the array, return False.

Complexity

time complexity: O(n) space complexity: O(min(n,k))

Implement

    class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        pos = {}
        for i, num in enumerate(nums):
            if num in pos and i - pos[num] <= k:
                return True
            pos[num] = i
        return False

    
    

Twitter  facebook  Email