LeetCode #219 Contains Duplicate II

Posted on | Post modified | In , , , , , ,

Problem

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Examples

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

Solution

Method: Hash Table

Time Complexity: O(n)

Space Complexity: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        table = {}

        for idx, num in enumerate(nums):
            if num in table and (idx - table[num]) <= k:
                return True
            else:
                table[num] = idx

        return False