Contains Duplicate II LeetCode

Key takeaways
We have an array of integers, nums, and an integer k representing the maximum allowed distance between duplicate values. Our task is to determine if there are two different indices with the same value within k positions of each other.
Use a set to track the values in the array as we iterate through it. For each value, check if it exists in the set; if it does, return true. If the set's size exceeds k, remove the oldest value to ensure only the most recent k indices are considered. If no duplicates are found by the end, return false.
The time complexity is $O(N)$ .
The space complexity is $O(K)$ .

The Contains Duplicate II is a common computer science problem that requires efficient finding of duplicates in an array. The LeetCode Contains Duplicate II focuses on manipulating the array to use in various real-world applications, such as data stream processing to detect duplicate entries within a certain window size, fraud detection, where detecting duplicate transactions within a short period of time is crucial and in server log analysis to find repeated error messages or events.

Algorithm

Let us now understand the algorithm. We will use a set and traverse the array. For every item, if that particular item is already stored in the set, we will return true. Otherwise, we will store that item in the set. After storing the item, we will check if the size of the set is greater than the value of k; if so, we will remove the oldest value from the set. This is done because we have to fulfill the condition abs(i - j) <= k; that is, the absolute value of the difference of i and j should not exceed the value of k. We will achieve this by removing the oldest value from the set to make sure that the set should always have values less than or equal to the value of k. After the loop terminates, we will return false, indicating that there is no duplicate.

Note: We will use a set instead of a hash map because the hash map requires a key and a value, whereas the set only needs a value. As we only need to keep track of the value, using a set makes more sense.

Here's how this approach works:

Start a loop controlled by a loop-control variable, e.g. i, to traverse the array.
For every iteration, perform the following steps:
- Check if the ith item is already stored in the set; if so, return true.
- Otherwise, put the ith item in the set.
- Check if the set's size becomes greater than the value of k; if so, remove the oldest value, nums[i—k], from the set.
If the loop ends, it means no duplicate is found, and we will return false.

Let's visualize the algorithm:

# Function to check if there is a duplicate in the array
# which fulfils the condition abs(i - j) <= k.
def contains_duplicate(nums, k):
    # Initialize a hash table
    set_ = set()
    # Start a loop which will run from 0 to the length of the nums
    for i in range(len(nums)):
        # Check if set contains nums[i], if so, return true
        if nums[i] in set_:
            return True
        # Otherwise, store nums[i] in the set
        set_.add(nums[i])
        # Check if the length of set becomes greater than the
        # value of k, if so, remove the oldest value from set
        if len(set_) > k:
            set_.remove(nums[i - k])
    # When the loop terminates, it means that there is no
    # duplicate in the array, and we will return false.
    return False
# Driver code
def main():
    input_list = [
    ([1, 2, 3, 1], 3),
    ([1, 0, 1, 1], 1),
    ([1, 2, 3, 4, 5], 2),
    ([1, 2, 3, 1, 2, 3], 2),
    ([1, 2, 3, 1, 5, 9, 2], 4)
]
    for i, (nums, k) in enumerate(input_list):
        result = contains_duplicate(nums, k)
        print(f"{i + 1}.\tInput: nums = {nums}, k = {k}")
        print(f"\tOutput: {result}")
        print('-' * 100)
if __name__ == "__main__":
    main();

Contains Duplicate II

Now that we have a solution for this LeetCode problem, let's analyze its time and space complexity.

Time complexity

In the worst case, we traverse the array from start to end, which will take $O(N)$ . We add or remove an item in the set in each loop iteration. Since adding or removing an item in the set takes constant time, i.e., $O(1)$ , the entire code will take $O(N∗1)$ , which is $O(N)$ .

Space complexity

The space complexity depends on the size of the set. As we remove the oldest value from the set whenever its size becomes greater than k, there will be $K + 1$ items in the set at max at any given time. Thus, the space complexity would be $O(K)$ .

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

YouTubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

Contains Duplicate II LeetCode

Problem statement

Knowledge test

Algorithm

Coding example

Time complexity

Space complexity