Jobs

Interviews

Discussions

Contains Duplicate II

Easy

Contains Duplicate II

Easy

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the values within the `nums` array, and for the integer `k`?
Can the `nums` array be empty or null?
If there are multiple pairs of indices (i, j) that satisfy the condition, do I need to return all of them, or is it sufficient to return `true` as soon as one such pair is found?
Is `k` always a non-negative integer? What happens if `k` is zero?
By "distinct indices", do you mean that `i` and `j` must be different, or is `i == j` a possibility?

Brute Force Solution

Approach

The brute force way to see if a collection of items has nearby duplicates is to simply check every possible pair of items. We compare each item to all other items within a certain distance to see if they are the same.

Here's how the algorithm would work step-by-step:

Take the first item in the collection.
Compare it to the next item in the collection. Check if these items are the same and if they are close enough to each other according to the given distance rule.
Compare the first item to the item after that, again checking if they are the same and close enough.
Keep comparing the first item to all the other items that are within the allowed distance.
Once you've checked the first item against all nearby items, move to the second item in the collection.
Repeat the process: compare the second item to all the items that come after it and are within the allowed distance, checking for sameness.
Continue this process, moving through each item in the collection and comparing it to all the items that follow it within the specified distance.
If, at any point, you find two items that are the same and close enough, you know the answer is yes. Otherwise, if you check all pairs and find nothing, the answer is no.

Code Implementation

def contains_duplicate_ii_brute_force(numbers, allowed_distance):
    for first_index in range(len(numbers)):

        # Iterate through elements after the current one
        for second_index in range(first_index + 1, len(numbers)):

            # Check for duplicate values
            if numbers[first_index] == numbers[second_index]:

                # Verify the distance constraint
                distance_between_indices = abs(first_index - second_index)

                # Return true if within allowed distance
                if distance_between_indices <= allowed_distance:
                    return True

    # No duplicates found within the distance
    return False

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n elements in the input array. For each element, it compares it to at most k subsequent elements where k is the given distance. In the worst-case scenario, for each of the n elements we potentially compare against all of the other n-1 elements, leading to nested loops. The approximate number of comparisons is then n * (n-1), which simplifies to n * n. Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The provided brute force algorithm only uses a few integer variables for indexing and comparison. It does not create any auxiliary data structures like arrays, hash maps, or lists to store intermediate results. The memory used by these integer variables remains constant irrespective of the input array size N. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The key is to remember the last time you saw each number. Instead of checking every pair of numbers, this method remembers recent sightings to quickly identify duplicates within a certain distance.

Here's how the algorithm would work step-by-step:

Imagine a notebook to jot down each number you see and the last time you saw it.
As you go through the list of numbers, check if you've seen the current number before in your notebook.
If you have, see if the current spot is close enough to the last spot you saw it (within the allowed distance).
If it's close enough, you've found a nearby duplicate, and you're done!
If it's not close enough, or if you haven't seen the number before, write down the current spot in your notebook, updating the last known location for that number.
Continue this process until you find a duplicate within the distance, or you reach the end of the list.

Code Implementation

def containsNearbyDuplicate(numbers, allowed_distance):
    last_seen_position = {}

    for index, number in enumerate(numbers):
        # Check if the current number has been seen before.
        if number in last_seen_position:

            distance = index - last_seen_position[number]

            # If the distance is within the allowed range, return True.
            if distance <= allowed_distance:
                return True

        # Update the last seen position of the current number.
        last_seen_position[number] = index

    return False

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the input array nums of size n once. In each iteration, it performs a constant-time operation: checking if the current number exists in the hash map (the 'notebook' referred to in the description) and updating the hash map with the number and its index. Therefore, the time complexity is directly proportional to the number of elements in the input array, resulting in a linear time complexity of O(n).

Space Complexity

O(N) – The algorithm uses a notebook (represented by a hash map or dictionary) to store each number encountered and its last seen index. In the worst-case scenario, all N numbers in the input array are unique, and each will be added to the notebook. Therefore, the space required grows linearly with the number of elements in the input array. Thus, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input array	Return false immediately, as there are no elements to compare.
k is zero	The indices i and j must be distinct, so return false if k is zero and no consecutive duplicates exist.
k is a large value (close to Integer.MAX_VALUE)	The solution should not overflow when calculating the absolute difference between indices.
Array contains only one element	Return false as we need two distinct indices to form a pair.
Array contains all identical elements	The solution should correctly identify duplicate indices within the distance k.
Array with large numbers and k is also large	The solution's performance shouldn't degrade significantly with large inputs.
No duplicates exist in the array	The solution should correctly return false when no duplicate elements exist within the specified range.
Array contains negative numbers	The solution should work correctly with negative numbers in the array.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the values within the `nums` array, and for the integer `k`?
Can the `nums` array be empty or null?
If there are multiple pairs of indices (i, j) that satisfy the condition, do I need to return all of them, or is it sufficient to return `true` as soon as one such pair is found?
Is `k` always a non-negative integer? What happens if `k` is zero?
By "distinct indices", do you mean that `i` and `j` must be different, or is `i == j` a possibility?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first item in the collection.
Compare it to the next item in the collection. Check if these items are the same and if they are close enough to each other according to the given distance rule.
Compare the first item to the item after that, again checking if they are the same and close enough.
Keep comparing the first item to all the other items that are within the allowed distance.
Once you've checked the first item against all nearby items, move to the second item in the collection.
Repeat the process: compare the second item to all the items that come after it and are within the allowed distance, checking for sameness.
Continue this process, moving through each item in the collection and comparing it to all the items that follow it within the specified distance.
If, at any point, you find two items that are the same and close enough, you know the answer is yes. Otherwise, if you check all pairs and find nothing, the answer is no.

Code Implementation

def contains_duplicate_ii_brute_force(numbers, allowed_distance):
    for first_index in range(len(numbers)):

        # Iterate through elements after the current one
        for second_index in range(first_index + 1, len(numbers)):

            # Check for duplicate values
            if numbers[first_index] == numbers[second_index]:

                # Verify the distance constraint
                distance_between_indices = abs(first_index - second_index)

                # Return true if within allowed distance
                if distance_between_indices <= allowed_distance:
                    return True

    # No duplicates found within the distance
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The key is to remember the last time you saw each number. Instead of checking every pair of numbers, this method remembers recent sightings to quickly identify duplicates within a certain distance.

Here's how the algorithm would work step-by-step:

Imagine a notebook to jot down each number you see and the last time you saw it.
As you go through the list of numbers, check if you've seen the current number before in your notebook.
If you have, see if the current spot is close enough to the last spot you saw it (within the allowed distance).
If it's close enough, you've found a nearby duplicate, and you're done!
If it's not close enough, or if you haven't seen the number before, write down the current spot in your notebook, updating the last known location for that number.
Continue this process until you find a duplicate within the distance, or you reach the end of the list.

Code Implementation

def containsNearbyDuplicate(numbers, allowed_distance):
    last_seen_position = {}

    for index, number in enumerate(numbers):
        # Check if the current number has been seen before.
        if number in last_seen_position:

            distance = index - last_seen_position[number]

            # If the distance is within the allowed range, return True.
            if distance <= allowed_distance:
                return True

        # Update the last seen position of the current number.
        last_seen_position[number] = index

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return false immediately, as there are no elements to compare.
k is zero	The indices i and j must be distinct, so return false if k is zero and no consecutive duplicates exist.
k is a large value (close to Integer.MAX_VALUE)	The solution should not overflow when calculating the absolute difference between indices.
Array contains only one element	Return false as we need two distinct indices to form a pair.
Array contains all identical elements	The solution should correctly identify duplicate indices within the distance k.
Array with large numbers and k is also large	The solution's performance shouldn't degrade significantly with large inputs.
No duplicates exist in the array	The solution should correctly return false when no duplicate elements exist within the specified range.
Array contains negative numbers	The solution should work correctly with negative numbers in the array.