Jobs

Interviews

Discussions

Contains Duplicate III

Hard

Netflix

16 views

Topics:

Arrays

You are given an integer array nums and two integers indexDiff and valueDiff.

Find a pair of indices (i, j) such that:

i != j,
abs(i - j) <= indexDiff.
abs(nums[i] - nums[j]) <= valueDiff, and

Return true if such pair exists or false otherwise.

Example 1:

Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

Example 2:

Input: nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
Output: false
Explanation: After trying all the possible pairs (i, j), we cannot satisfy the three conditions, so we return false.

Constraints:

2 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
1 <= indexDiff <= nums.length
0 <= valueDiff <= 10⁹

Contains Duplicate III

Hard

Netflix

16 views

Topics:

Arrays

You are given an integer array nums and two integers indexDiff and valueDiff.

Find a pair of indices (i, j) such that:

i != j,
abs(i - j) <= indexDiff.
abs(nums[i] - nums[j]) <= valueDiff, and

Return true if such pair exists or false otherwise.

Example 1:

Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

Example 2:

Input: nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
Output: false
Explanation: After trying all the possible pairs (i, j), we cannot satisfy the three conditions, so we return false.

Constraints:

2 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
1 <= indexDiff <= nums.length
0 <= valueDiff <= 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 values in the `nums` array, and for `k` and `t`?
Can `nums` be empty, or can `k` or `t` be zero or negative?
If multiple pairs (i, j) satisfy the conditions, do I need to return all of them, or is finding just one sufficient?
Are there any specific data type considerations I should be aware of, such as the possibility of integer overflow when calculating the absolute difference?
By 'distinct indices i and j', does it mean that i must not equal j?

Brute Force Solution

Approach

The brute force strategy for determining if almost duplicate numbers exist within a certain range is to simply compare every possible pair of numbers. We'll examine all the numbers and check if any other number within the range is similar to it. This is like meticulously comparing each item in a collection against all the others to find a match that fits our criteria.

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

Take the first number from the list.
Compare it to every other number within the specified distance.
For each comparison, check if the difference between the two numbers is small enough.
If the difference is small enough, then we have found almost duplicate numbers within the distance, and we are done.
If we didn't find a match, repeat the above steps with the next number in the list.
Continue this process until we have compared all the numbers in the list to those within the distance.
If we still haven't found a match after comparing all the numbers, then there are no almost duplicate numbers within the given distance.

Code Implementation

def contains_duplicate_iii_brute_force(numbers, index_distance, value_distance):
    list_length = len(numbers)

    for first_index in range(list_length):
        # Outer loop iterates through each element

        for second_index in range(first_index + 1, min(list_length, first_index + index_distance + 1)):
            # Check neighbors within index_distance

            if abs(numbers[first_index] - numbers[second_index]) <= value_distance:
                # Value diff within value_distance
                return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n numbers in the input array. For each number, it compares it with up to k other numbers within a distance of k. In the worst-case scenario, k is close to n, resulting in nested loops where the outer loop iterates n times and the inner loop iterates up to n times in the worst case. Therefore, the number of comparisons approaches n multiplied by n. This results in approximately n * n comparisons, which simplifies to O(n²).

Space Complexity

O(1) – The provided algorithm, described in plain English, iterates through the input list and compares numbers within a specified distance. It does not create any auxiliary data structures like lists, hash maps, or sets to store intermediate results or track visited elements. The algorithm only uses a fixed number of variables for indices and comparisons, independent of the input size N (the length of the input list). Therefore, the space complexity remains constant regardless of the input size.

Optimal Solution

Approach

The goal is to quickly find if there are two numbers within a certain distance of each other that are also close in value. We avoid checking all pairs by organizing the numbers into groups based on their values, allowing us to only compare numbers within the relevant groups.

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

Imagine dividing the number line into equal-sized sections or 'buckets', where the size of each section is determined by how close in value the numbers need to be.
For each number in the list, figure out which section it belongs to based on its value.
Check if the section already has a number in it. If it does, then we've found two numbers that meet the criteria, and we can stop.
If the section is empty, check the neighboring sections to see if there's a number that is close enough in value to our current number.
If a neighboring section has a number that's close enough, we've found a pair that meets the requirements. If not, we continue to the next number.
If we go through all the numbers and don't find any qualifying pairs, it means there are no such numbers that satisfy the conditions.

Code Implementation

def containsNearbyAlmostDuplicate(numbers, index_difference, value_difference):
    if index_difference < 1 or value_difference < 0:
        return False

    value_map = {}

    for index, number in enumerate(numbers):
        bucket_number = number // (value_difference + 1)

        # Check if bucket exists, implies near duplicate
        if bucket_number in value_map:
            return True

        # Check adjacent buckets for near duplicates
        if (bucket_number - 1) in value_map and \
           abs(number - value_map[bucket_number - 1]) <= value_difference:
            return True

        if (bucket_number + 1) in value_map and \
           abs(number - value_map[bucket_number + 1]) <= value_difference:
            return True

        value_map[bucket_number] = number

        # Maintain window size based on index_difference
        if index >= index_difference:

            number_to_remove = numbers[index - index_difference]
            bucket_to_remove = number_to_remove // (value_difference + 1)
            del value_map[bucket_to_remove]

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the n numbers in the input array nums. Inside the loop, it calculates the bucket ID in O(1) time. Then, it performs a constant number of operations: checking the current and neighboring buckets in the hash map. The insertion and deletion operations in the hash map also take O(1) time on average. Therefore, the dominant operation is iterating through the array once, resulting in O(n) time complexity.

Space Complexity

O(min(N, k)) – The algorithm uses a hash map (or dictionary) to store elements within the sliding window of size k. In the worst case, the hash map will store at most k elements if all elements within the window are distinct. However, if the input array has fewer than k elements, the hash map will store at most N elements, where N is the number of elements in the input array. Thus, the space complexity is bounded by the minimum of N and k. This translates to a space complexity of O(min(N, k)).

Edge Cases

Case	How to Handle
Empty input array	Return false immediately because no indices exist.
k is zero	Check if t >= abs(nums[i] - nums[i]), which is equivalent to t >= 0, return true if so, else false if input has more than 1 element.
t is zero	Check if there are duplicate numbers within the range k, return true if found.
Large k value exceeding array bounds	The solution should not access array elements out of bounds; k effectively becomes array length - 1.
Large t value that causes integer overflow in difference calculation	Use long type or appropriate comparison methods to prevent integer overflow.
Array containing all identical elements	The solution correctly handles identical elements by checking indices within range k.
Negative numbers in the array	Absolute difference handles negative numbers correctly.
Extreme boundary values (e.g., Integer.MAX_VALUE, Integer.MIN_VALUE)	Use long type or carefully order operations to avoid overflow when calculating absolute differences.

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 in the `nums` array, and for `k` and `t`?
Can `nums` be empty, or can `k` or `t` be zero or negative?
If multiple pairs (i, j) satisfy the conditions, do I need to return all of them, or is finding just one sufficient?
Are there any specific data type considerations I should be aware of, such as the possibility of integer overflow when calculating the absolute difference?
By 'distinct indices i and j', does it mean that i must not equal j?

Brute Force Solution

Approach

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

Take the first number from the list.
Compare it to every other number within the specified distance.
For each comparison, check if the difference between the two numbers is small enough.
If the difference is small enough, then we have found almost duplicate numbers within the distance, and we are done.
If we didn't find a match, repeat the above steps with the next number in the list.
Continue this process until we have compared all the numbers in the list to those within the distance.
If we still haven't found a match after comparing all the numbers, then there are no almost duplicate numbers within the given distance.

Code Implementation

def contains_duplicate_iii_brute_force(numbers, index_distance, value_distance):
    list_length = len(numbers)

    for first_index in range(list_length):
        # Outer loop iterates through each element

        for second_index in range(first_index + 1, min(list_length, first_index + index_distance + 1)):
            # Check neighbors within index_distance

            if abs(numbers[first_index] - numbers[second_index]) <= value_distance:
                # Value diff within value_distance
                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:

Imagine dividing the number line into equal-sized sections or 'buckets', where the size of each section is determined by how close in value the numbers need to be.
For each number in the list, figure out which section it belongs to based on its value.
Check if the section already has a number in it. If it does, then we've found two numbers that meet the criteria, and we can stop.
If the section is empty, check the neighboring sections to see if there's a number that is close enough in value to our current number.
If a neighboring section has a number that's close enough, we've found a pair that meets the requirements. If not, we continue to the next number.
If we go through all the numbers and don't find any qualifying pairs, it means there are no such numbers that satisfy the conditions.

Code Implementation

def containsNearbyAlmostDuplicate(numbers, index_difference, value_difference):
    if index_difference < 1 or value_difference < 0:
        return False

    value_map = {}

    for index, number in enumerate(numbers):
        bucket_number = number // (value_difference + 1)

        # Check if bucket exists, implies near duplicate
        if bucket_number in value_map:
            return True

        # Check adjacent buckets for near duplicates
        if (bucket_number - 1) in value_map and \
           abs(number - value_map[bucket_number - 1]) <= value_difference:
            return True

        if (bucket_number + 1) in value_map and \
           abs(number - value_map[bucket_number + 1]) <= value_difference:
            return True

        value_map[bucket_number] = number

        # Maintain window size based on index_difference
        if index >= index_difference:

            number_to_remove = numbers[index - index_difference]
            bucket_to_remove = number_to_remove // (value_difference + 1)
            del value_map[bucket_to_remove]

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return false immediately because no indices exist.
k is zero	Check if t >= abs(nums[i] - nums[i]), which is equivalent to t >= 0, return true if so, else false if input has more than 1 element.
t is zero	Check if there are duplicate numbers within the range k, return true if found.
Large k value exceeding array bounds	The solution should not access array elements out of bounds; k effectively becomes array length - 1.
Large t value that causes integer overflow in difference calculation	Use long type or appropriate comparison methods to prevent integer overflow.
Array containing all identical elements	The solution correctly handles identical elements by checking indices within range k.
Negative numbers in the array	Absolute difference handles negative numbers correctly.
Extreme boundary values (e.g., Integer.MAX_VALUE, Integer.MIN_VALUE)	Use long type or carefully order operations to avoid overflow when calculating absolute differences.