Contains Duplicate II

In this problem, we want to find if 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 less than or equal to k.

We can solve this problem by using a hash table to store the last index where each number was seen. We’ll iterate through the array and for each number, check if we’ve seen it before and if the difference between the current index and the last index where it was seen is less than or equal to k. If both conditions are true, we’ll return true. If not, we’ll update the hash table with the current index and continue.

Here’s the implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

from typing import List

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        num_indices = {}

        for i, num in enumerate(nums):
            if num in num_indices and i - num_indices[num] <= k:
                return True
            num_indices[num] = i

        return False

This solution iterates through the array once, making the time complexity O(n), where n is the length of the array. The space complexity is also O(n), as in the worst case, we might store all the elements in the hash table.

10 Prerequisite LeetCode Problems

“Contains Duplicate II” focuses on the usage of Hashmaps/Hashsets, and maintaining a sliding window concept. Here are 10 simpler problems to practice as a foundation:

  1. 217. Contains Duplicate: This is a simpler version of Contains Duplicate II, and it will help you to understand how to detect duplicates using a HashSet.

  2. 349. Intersection of Two Arrays: This problem helps to understand how to use HashSets to find common elements in two arrays.

  3. 202. Happy Number: This problem uses a HashSet to remember previously seen numbers in a sequence.

  4. 141. Linked List Cycle: Even though this problem deals with linked lists, the principle of using a HashSet to detect duplicates is the same.

  5. 219. Contains Duplicate III: This problem is a bit more complex than Contains Duplicate II, but if you can understand and solve this one, Contains Duplicate II will be easier.

  6. 1. Two Sum: This problem involves using a HashMap to track previous elements in an array and their indices, similar to Contains Duplicate II.

  7. 705. Design HashSet: This problem helps you understand the underlying functionality of a HashSet, which is a crucial part of solving Contains Duplicate II.

  8. 594. Longest Harmonious Subsequence: This problem also uses a HashMap and has a similar flavor to the Contains Duplicate problems.

  9. 760. Find Anagram Mappings: It helps you understand how to use Hashmaps to track indices of elements, a useful tool in Contains Duplicate II.

  10. 532. K-diff Pairs in an Array: This problem shares a similar concept where you need to find pairs within a certain difference.

These cover how to use HashSets and HashMaps, which are the main data structures needed for Contains Duplicate II.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        hset = {}

        for idx in range(len(nums)):
            if nums[idx] in hset and abs(idx - hset[nums[idx]]) <= k:
                return True
            hset[nums[idx]] = idx

        return False

Problem Classification

  1. Array/Sequence Processing: The problem statement revolves around handling a list (or array) of integers, which implies the need for techniques related to array manipulation and traversal.

  2. Searching: It requires determining if there are duplicate elements present in the list within a certain distance (or range) from each other, implying the necessity of search operations.

  3. HashMap/Dictionary Usage: The usage of data structures like HashMap or dictionary is suggested by the need to track the index of elements in the list, and then use these indices for comparison. This implies the concept of key-value pairing, as used in HashMaps or dictionaries.

  4. Distance Measurement: The need to check whether duplicates are within a certain distance or range from each other indicates the application of mathematical operations and comparisons.

These classifications are based on the concepts and strategies used to solve the problem, and not on any specific implementation or language-specific details.

Clarification Questions

What are the clarification questions we can ask about this problem?

Identifying Problem Isomorphism

“Contains Duplicate II” can be mapped to “Minimum Size Subarray Sum”.

Both problems deal with contiguous subarrays and certain conditions they need to fulfill. In “Contains Duplicate II”, we need to find if there exist two indices i and j such that the absolute difference of i and j is at most k and the values at these indices are the same. In “Minimum Size Subarray Sum”, we need to find the minimal length of a contiguous subarray of which the sum is greater than or equal to a target integer.

In both cases, you might use a sliding window approach. In “Contains Duplicate II”, the window can shrink when a value is repeated within the defined range. In “Minimum Size Subarray Sum”, the window shrinks when the sum is larger than or equal to the target.

“Contains Duplicate II” is simpler because it only involves checking for duplicate elements within a certain range, whereas “Minimum Size Subarray Sum” involves checking for subarrays that meet a particular sum condition.

Language Agnostic Coding Drills

  1. Understanding Lists/Arrays: Understanding how to iterate through the elements of a list or array and how to access individual elements based on their index.

  2. Dictionary Operations: Understanding how to create a dictionary, add key-value pairs to it, and check for the existence of a key. Also, understanding how to update the value associated with a key.

  3. If-Else Statements: Understanding how to use if-else conditions to perform different operations based on the condition’s outcome.

  4. Loops: Understanding how to use loops for repeated operations. Here, we’re using a for loop to iterate over the array.

  5. Understanding of Abs Function: Understanding the built-in abs function, which returns the absolute value of the number.

  6. Logical Operations: Understanding how to use logical operators, particularly the and operator and the <= operator.

Step by step approach to solve the problem:

  1. Start with an empty dictionary hset.

  2. Iterate over the input array nums with a for loop, with the index variable being idx.

  3. In each iteration, first check if the current number nums[idx] already exists in the dictionary hset and if the absolute difference between the current index idx and the stored index in hset is less than or equal to k.

  4. If the above condition is true, return True.

  5. If the current number does not exist in the dictionary or the condition in step 3 is not met, add the current number as a key to the dictionary hset, with its value being the current index idx.

  6. If the loop finishes without returning True, it means no such pair of duplicates was found, so return False.

This problem-solving approach requires knowledge of lists/arrays, dictionaries, loops, if-else statements, and basic mathematical functions and operators. It provides a good exercise for practicing these concepts and building a fundamental understanding of how they can be combined to solve more complex problems.

Targeted Drills in Python

  1. Understanding Lists/Arrays

    Create a list of integers and print each item with its index.

    1
2
3

    numbers = [1, 2, 3, 4, 5]
for idx, num in enumerate(numbers):
    print(f"Index: {idx}, Value: {num}")

  2. Dictionary Operations

    Create a dictionary from a list of integers where the integer is the key and its square is the value.

    1
2
3

    numbers = [1, 2, 3, 4, 5]
squares = {num: num ** 2 for num in numbers}
print(squares)

  3. If-Else Statements

    Check if a number exists in the dictionary, if it does print its value else print a message.

    1
2
3
4
5
6

    squares = {1: 1, 2: 4, 3: 9, 4: 16, 5: 25}
num = 3
if num in squares:
    print(squares[num])
else:
    print(f"{num} not in dictionary")

  4. Loops

    Print the first 5 even numbers.

    1
2

    for i in range(2, 11, 2):
    print(i)

  5. Understanding of Abs Function

    Print the absolute difference between two numbers.

    1
2
3

    num1 = 5
num2 = 10
print(abs(num1 - num2))

  6. Logical Operations

    Check if a number is within a certain range.

    1
2
3
4
5

    num = 7
if num >= 5 and num <= 10:
    print("Number is within range")
else:
    print("Number is out of range")

You can practice these drills individually to get a grasp on each concept. After you’re comfortable with each of them, you can combine these concepts to solve the original problem.