Jobs

Interviews

Discussions

Contains Duplicate II

Easy

Netflix

6 views

Topics:

Arrays

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 1:

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

Example 2:

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

Example 3:

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

Constraints:

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
0 <= k <= 10⁵

Contains Duplicate II

Easy

Netflix

6 views

Topics:

Arrays

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 1:

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

Example 2:

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

Example 3:

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

Constraints:

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
0 <= k <= 10⁵

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 integers within the `nums` array, and what is the maximum size of the `nums` array?
Can the value of `k` be negative, zero, or larger than the size of the `nums` array?
If there are multiple pairs of indices (i, j) that satisfy the condition, do I need to return all such pairs, or is it sufficient to return `true` as soon as I find one?
Is the array guaranteed to be non-empty, or should I handle the case where `nums` is null or empty?
Are the indices `i` and `j` required to be different, or can `i` and `j` be the same as long as `nums[i] == nums[j]` and `abs(i - j) <= k`?

Brute Force Solution

Approach

We want to find if there are two identical items close to each other in a list. The brute force method is like comparing every item with every other item in the list to see if they are the same and close enough.

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

Take the first item in the list.
Compare it with every other item that follows it in the list, up to a certain distance away.
If you find another item that is the same as the first one and within the specified distance, then you've found a duplicate pair that meets the criteria; you're done.
If you don't find a matching item within that distance, move on to the second item in the original list.
Now repeat the same comparison process for this second item with every item that follows it within the allowed distance.
Keep doing this, moving through each item in the original list and comparing it to the items that follow it within the specified distance, until you either find a matching pair or you've checked every item in the list.

Code Implementation

def contains_duplicate_ii_brute_force(numbers, maximum_distance):
    list_length = len(numbers)

    for first_index in range(list_length):
        # Iterate through each element in the list.

        for second_index in range(first_index + 1, list_length):
            # Compare each number to all other numbers that follow.

            if numbers[first_index] == numbers[second_index]:
                # Check to see if the elements are the same

                distance = abs(first_index - second_index)

                if distance <= maximum_distance:
                    # Check if the indices are close enough.
                    return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force solution iterates through the array of size n. For each element, it compares it with up to k subsequent elements where k <= n. In the worst-case scenario where k is close to n, for each of the n elements, we perform roughly n comparisons. This leads to approximately n * n comparisons, therefore the time complexity is O(n²).

Space Complexity

O(1) – The provided algorithm iterates through the list and compares elements within a specified distance. It does not utilize any auxiliary data structures such as lists, hash maps, or sets to store intermediate results. Only a few constant space variables (indices) are needed for comparison, and their number does not depend on the input size N. Therefore, the algorithm's space complexity is constant, O(1).

Optimal Solution

Approach

We want to quickly determine if there are two identical numbers within a certain distance of each other. The key idea is to remember the recent locations of numbers we've seen, so we don't have to search through the entire list every time.

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

Create a way to remember the last place we saw each number.
Go through the list of numbers one at a time.
For each number, check if we've seen it before and if it's within the allowed distance from where we saw it last time.
If it is, we've found a duplicate within the distance, so the answer is yes.
If not, remember the current location of this number, so we can check it later.
If we get through the entire list without finding a duplicate within the distance, the answer is no.

Code Implementation

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

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

            #Check the distance between the current and previous index
            distance = index - last_seen_index[number]
            if distance <= allowed_distance:
                return True

        # Store the current index of the number.
        last_seen_index[number] = index

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the input array of size n exactly once. Inside the loop, it performs constant-time operations such as checking a hash map and updating the hash map. Therefore, the time complexity is determined by the single pass through the array, resulting in O(n) time complexity.

Space Complexity

O(N) – The provided solution uses a data structure, as mentioned in step 1, to remember the last place each number was seen. This likely involves a hash map (or dictionary) where each unique number in the input array nums is stored as a key, and its index is stored as the value. In the worst case, all N elements in nums are unique, leading to N entries in the hash map. Therefore, the auxiliary space used grows linearly with the number of elements in the input array, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty or null input array	Return false immediately since no duplicates can exist.
k is zero	The algorithm should return false unless there are two identical values at the same index (which is impossible) in which case our algorithm should not crash.
k is negative	The algorithm should treat k as 0 or throw an exception.
Array with a single element	Return false immediately, as there cannot be two distinct indices.
Large input array with all same values and large k	Ensure the solution's time complexity is efficient, such as O(n) using a hash map, to avoid timeouts.
Large k value (k > array length)	The algorithm should function correctly, effectively searching the entire array for duplicates.
Array with integer overflow values	The algorithm's integer subtraction for index difference should not cause issues if the indices are reasonably sized (within normal integer bounds).
Array with large range and many duplicates far apart	The sliding window approach should efficiently iterate through and not consume excessive memory with large hashmap.

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 integers within the `nums` array, and what is the maximum size of the `nums` array?
Can the value of `k` be negative, zero, or larger than the size of the `nums` array?
If there are multiple pairs of indices (i, j) that satisfy the condition, do I need to return all such pairs, or is it sufficient to return `true` as soon as I find one?
Is the array guaranteed to be non-empty, or should I handle the case where `nums` is null or empty?
Are the indices `i` and `j` required to be different, or can `i` and `j` be the same as long as `nums[i] == nums[j]` and `abs(i - j) <= k`?

Brute Force Solution

Approach

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

Take the first item in the list.
Compare it with every other item that follows it in the list, up to a certain distance away.
If you find another item that is the same as the first one and within the specified distance, then you've found a duplicate pair that meets the criteria; you're done.
If you don't find a matching item within that distance, move on to the second item in the original list.
Now repeat the same comparison process for this second item with every item that follows it within the allowed distance.
Keep doing this, moving through each item in the original list and comparing it to the items that follow it within the specified distance, until you either find a matching pair or you've checked every item in the list.

Code Implementation

def contains_duplicate_ii_brute_force(numbers, maximum_distance):
    list_length = len(numbers)

    for first_index in range(list_length):
        # Iterate through each element in the list.

        for second_index in range(first_index + 1, list_length):
            # Compare each number to all other numbers that follow.

            if numbers[first_index] == numbers[second_index]:
                # Check to see if the elements are the same

                distance = abs(first_index - second_index)

                if distance <= maximum_distance:
                    # Check if the indices are close enough.
                    return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Create a way to remember the last place we saw each number.
Go through the list of numbers one at a time.
For each number, check if we've seen it before and if it's within the allowed distance from where we saw it last time.
If it is, we've found a duplicate within the distance, so the answer is yes.
If not, remember the current location of this number, so we can check it later.
If we get through the entire list without finding a duplicate within the distance, the answer is no.

Code Implementation

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

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

            #Check the distance between the current and previous index
            distance = index - last_seen_index[number]
            if distance <= allowed_distance:
                return True

        # Store the current index of the number.
        last_seen_index[number] = index

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return false immediately since no duplicates can exist.
k is zero	The algorithm should return false unless there are two identical values at the same index (which is impossible) in which case our algorithm should not crash.
k is negative	The algorithm should treat k as 0 or throw an exception.
Array with a single element	Return false immediately, as there cannot be two distinct indices.
Large input array with all same values and large k	Ensure the solution's time complexity is efficient, such as O(n) using a hash map, to avoid timeouts.
Large k value (k > array length)	The algorithm should function correctly, effectively searching the entire array for duplicates.
Array with integer overflow values	The algorithm's integer subtraction for index difference should not cause issues if the indices are reasonably sized (within normal integer bounds).
Array with large range and many duplicates far apart	The sliding window approach should efficiently iterate through and not consume excessive memory with large hashmap.