Leetcode – Contains Duplicate II Solution in Python

Introduction

The Contains Duplicate II problem is an extension of the Contains Duplicate problem, bringing in an additional constraint to consider when seeking duplicates in an array. As aspiring programmers or seasoned professionals, tackling such algorithmic challenges is pivotal for honing problem-solving skills. In this extensive guide, we will dissect the Contains Duplicate II problem on LeetCode, explore different methodologies to solve it, and evaluate their efficiencies through Python implementations.

Problem Description

The Contains Duplicate II problem (LeetCode #219) is defined as follows:

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

This problem requires us to determine if there are any duplicates within a given range in the array.

Approach 1: Brute Force

The simplest approach is to use nested loops to compare each element with every other element within the given range.

def containsNearbyDuplicate(nums, k):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, i + k + 1):
            if j < n and nums[i] == nums[j]:
                return True
    return False

This approach has a time complexity of O(nk) and a space complexity of O(1).

Approach 2: Using a Hash Set with Sliding Window

We can use a hash set to keep track of the numbers in the current window of size k. As we iterate through the array, we add the current number to the set. If the size of the window exceeds k, we remove the element that is now out of the window from the set.

def containsNearbyDuplicate(nums, k):
    # The set will store the elements in the current window
    seen = set()
    
    # Iterate through the array
    for i, num in enumerate(nums):
        # If the number is in the set, a duplicate is found within the range
        if num in seen:
            return True
        
        # Add the current number to the set
        seen.add(num)
        
        # If the size of the window exceeds k, remove the leftmost element
        if i >= k:
            seen.remove(nums[i - k])
    
    return False

This approach has a time complexity of O(n) and a space complexity of O(min(n, k)).

Approach 3: Using a Hash Map

Using a hash map, we can keep track of the indices of the elements. As we iterate through the array, if the current number is in the hash map and the difference between the indices is less than or equal to k, then we return True.

def containsNearbyDuplicate(nums, k):
    # The map stores the index of each element
    indices = {}
    
    # Iterate through the array
    for i, num in enumerate(nums):
        # Check if the current number is in the map and the difference in indices is <= k
        if num in indices and i - indices[num] <= k:
            return True
        
        # Update the index of the current number in the map
        indices[num] = i
    
    return False

This approach has a time complexity of O(n) and a space complexity of O(n).

Testing the Solutions

To ensure the accuracy of these solutions, you can call the function with an input array and value of k.

# Example
nums = [1, 2, 3, 4, 5, 2]
k = 3
print(containsNearbyDuplicate(nums, k))  # Output: False

Conclusion

The Contains Duplicate II problem builds on the Contains Duplicate problem by introducing an additional constraint. In this article, we covered brute force, sliding window, and hash map approaches, each with varying efficiencies. Opting for a hash set with sliding windows or employing a hash map is advisable due to their linear time complexities.