Jobs

Interviews

Discussions

Contains Duplicate II

Easy

Asked by:

More companies

135 views

Topics:

ArraysSliding Windows

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⁵

Try coding it in LeetCode

Contains Duplicate II

Easy

Asked by:

More companies

135 views

Topics:

ArraysSliding Windows

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⁵

Try coding it in LeetCode

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 constraints on the size of the input array `nums` and the value of `k`? Specifically, can `k` be negative, zero, or larger than the array's length?
What is the range of values for the integers within the `nums` array? Can they be negative or zero?
What should be the expected output if the input array `nums` is empty or contains only a single element?
The problem states 'two distinct indices'. To confirm, this means if `nums[i] == nums[j]`, we're looking for cases where `i` is not equal to `j`, correct?
Does the value of `k` represent the maximum inclusive difference? For example, if `k` is 1, does that mean we're looking for adjacent equal elements?

Brute Force Solution

Approach

The brute force strategy is to check every single number in the collection against every other number that comes after it. For each pair of numbers, we check if they are the same and also if their positions are close enough to each other.

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

Pick the very first number in the list.
Compare this first number to every other number that appears later in the list, one by one.
For each comparison, if the two numbers are identical, check how far apart their original positions are.
If their positions are within the allowed distance, you've found a match, and you can stop because the answer is yes.
If you compare the first number to all the others and don't find a close match, move on.
Now, pick the second number in the list and repeat the whole process: compare it against every number that comes after it.
Continue this process, taking each number in turn and comparing it to all the ones that follow it.
If you go through all possible pairings without finding two identical numbers that are close enough, then the answer is no.

Code Implementation

def contains_nearby_duplicate_brute_force(numbers_list, maximum_distance):
    number_of_elements = len(numbers_list)

    # Iterate through each number to select it as the first one for comparison.
    for first_index in range(number_of_elements):

        # Compare the selected number with every subsequent number in the list.
        for second_index in range(first_index + 1, number_of_elements):
            
            # If two numbers are identical, we then check if their indices are close enough.
            if numbers_list[first_index] == numbers_list[second_index]:
                position_difference = second_index - first_index
                
                # If the distance is within the allowed limit, we have found a valid pair.
                if position_difference <= maximum_distance:
                    return True

    # If the loops complete without finding a valid pair, no such duplicate exists.
    return False

Big(O) Analysis

Time Complexity

O(n²) – The time complexity is determined by the nested process of comparing pairs of numbers. The outer process iterates through each of the n elements in the list to select a number. For each selected number, an inner process compares it against all subsequent elements in the list. The first number is compared with n-1 others, the second with n-2, and so on. This pattern of comparisons results in a total number of operations that approximates n * (n-1) / 2. Therefore, the overall time complexity simplifies to O(n²).

Space Complexity

O(1) – The brute-force approach described does not require any auxiliary data structures like hash maps or extra arrays to store information. The algorithm operates by using a few variables to keep track of the current positions (indices) being compared. Since the number of these variables remains constant regardless of the input size N, the auxiliary space complexity is O(1).

Optimal Solution

Approach

Instead of checking every possible pair of numbers, we can process the list one number at a time, keeping track of the most recent location of each number we've seen. This allows us to instantly check if an identical number has appeared nearby without re-scanning.

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

Imagine you have a notepad to remember where you last saw each unique number.
Go through the list of numbers one by one, from beginning to end.
For each number you encounter, first check your notepad to see if you've seen this exact number before.
If you have seen it before, measure the distance between its current spot and the spot you wrote down on your notepad.
If this distance is small enough (within the allowed separation), you've found a nearby duplicate and you can stop immediately. The answer is 'yes'.
If the distance is too large, or if you've never seen this number before, just update your notepad with the current number and its new location.
Continue this process for every number in the list.
If you get all the way to the end of the list without finding any nearby duplicates, then the answer is 'no'.

Code Implementation

def containsNearbyDuplicate(numbers_list, max_separation):    # This notepad stores the most recent index seen for each unique number.    last_seen_location_of_number = {}    for current_index, current_number in enumerate(numbers_list):        # Check if we've seen this number before to evaluate the distance.        if current_number in last_seen_location_of_number:            previous_index = last_seen_location_of_number[current_number]            distance = current_index - previous_index            # If the distance is within the allowed separation, we've found a nearby duplicate.            if distance <= max_separation:                return True        # Update the notepad with the current number's most recent location.        last_seen_location_of_number[current_number] = current_index    return False

Big(O) Analysis

Time Complexity

O(n) – The solution processes the list of numbers, which has a size of n, in a single pass from beginning to end. For each of the n numbers, it performs a constant number of operations: checking for the number's existence and its last seen location in a hash map, and then updating the map with the current location. Since these hash map operations (lookup and insertion) take, on average, constant time, the total work is directly proportional to the number of elements in the list, resulting in a linear O(n) time complexity.

Space Complexity

O(min(N, K)) – The space complexity is determined by the "notepad" used to store the most recent location of each unique number. This notepad is implemented as a hash map. In the worst-case scenario, where all numbers are unique, the hash map could grow to store up to N entries, where N is the total number of elements in the input list. However, because we only care about duplicates within a distance of K, we can also think of this as a sliding window of size K, meaning the hash map would hold at most K+1 unique elements. Therefore, the space required is proportional to the smaller of N and K.

Edge Cases

Case	How to Handle
Empty input array	The solution should return false immediately as no pairs of indices can be formed.
Array with a single element	The solution should return false as there are no two distinct indices to compare.
The value of k is 0	The solution must return false, because the indices must be distinct, so their absolute difference can never be zero.
The value of k is negative	The solution should return false, as the absolute difference between indices cannot be less than or equal to a negative number.
Array contains no duplicates at all	The solution will correctly iterate through the entire array and return false at the end.
Duplicates exist, but their index difference is greater than k	The solution correctly identifies the duplicates but returns false because the index distance condition is never met.
All elements in the array are identical	The solution should return true as long as k is 1 or greater and the array has at least two elements.
Large input array size with a large k	An efficient solution using a hash map or a sliding window with a set ensures linear time complexity, avoiding a timeout.

Empty input array

How to Handle:

The solution should return false immediately as no pairs of indices can be formed.

Array with a single element

How to Handle:

The solution should return false as there are no two distinct indices to compare.

The value of k is 0

How to Handle:

The solution must return false, because the indices must be distinct, so their absolute difference can never be zero.

The value of k is negative

How to Handle:

The solution should return false, as the absolute difference between indices cannot be less than or equal to a negative number.

Array contains no duplicates at all

How to Handle:

The solution will correctly iterate through the entire array and return false at the end.

Duplicates exist, but their index difference is greater than k

How to Handle:

The solution correctly identifies the duplicates but returns false because the index distance condition is never met.

All elements in the array are identical

How to Handle:

The solution should return true as long as k is 1 or greater and the array has at least two elements.

Large input array size with a large k

How to Handle:

An efficient solution using a hash map or a sliding window with a set ensures linear time complexity, avoiding a timeout.

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 constraints on the size of the input array `nums` and the value of `k`? Specifically, can `k` be negative, zero, or larger than the array's length?
What is the range of values for the integers within the `nums` array? Can they be negative or zero?
What should be the expected output if the input array `nums` is empty or contains only a single element?
The problem states 'two distinct indices'. To confirm, this means if `nums[i] == nums[j]`, we're looking for cases where `i` is not equal to `j`, correct?
Does the value of `k` represent the maximum inclusive difference? For example, if `k` is 1, does that mean we're looking for adjacent equal elements?

Brute Force Solution

Approach

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

Pick the very first number in the list.
Compare this first number to every other number that appears later in the list, one by one.
For each comparison, if the two numbers are identical, check how far apart their original positions are.
If their positions are within the allowed distance, you've found a match, and you can stop because the answer is yes.
If you compare the first number to all the others and don't find a close match, move on.
Now, pick the second number in the list and repeat the whole process: compare it against every number that comes after it.
Continue this process, taking each number in turn and comparing it to all the ones that follow it.
If you go through all possible pairings without finding two identical numbers that are close enough, then the answer is no.

Code Implementation

def contains_nearby_duplicate_brute_force(numbers_list, maximum_distance):
    number_of_elements = len(numbers_list)

    # Iterate through each number to select it as the first one for comparison.
    for first_index in range(number_of_elements):

        # Compare the selected number with every subsequent number in the list.
        for second_index in range(first_index + 1, number_of_elements):
            
            # If two numbers are identical, we then check if their indices are close enough.
            if numbers_list[first_index] == numbers_list[second_index]:
                position_difference = second_index - first_index
                
                # If the distance is within the allowed limit, we have found a valid pair.
                if position_difference <= maximum_distance:
                    return True

    # If the loops complete without finding a valid pair, no such duplicate exists.
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you have a notepad to remember where you last saw each unique number.
Go through the list of numbers one by one, from beginning to end.
For each number you encounter, first check your notepad to see if you've seen this exact number before.
If you have seen it before, measure the distance between its current spot and the spot you wrote down on your notepad.
If this distance is small enough (within the allowed separation), you've found a nearby duplicate and you can stop immediately. The answer is 'yes'.
If the distance is too large, or if you've never seen this number before, just update your notepad with the current number and its new location.
Continue this process for every number in the list.
If you get all the way to the end of the list without finding any nearby duplicates, then the answer is 'no'.

Code Implementation

def containsNearbyDuplicate(numbers_list, max_separation):    # This notepad stores the most recent index seen for each unique number.    last_seen_location_of_number = {}    for current_index, current_number in enumerate(numbers_list):        # Check if we've seen this number before to evaluate the distance.        if current_number in last_seen_location_of_number:            previous_index = last_seen_location_of_number[current_number]            distance = current_index - previous_index            # If the distance is within the allowed separation, we've found a nearby duplicate.            if distance <= max_separation:                return True        # Update the notepad with the current number's most recent location.        last_seen_location_of_number[current_number] = current_index    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	The solution should return false immediately as no pairs of indices can be formed.
Array with a single element	The solution should return false as there are no two distinct indices to compare.
The value of k is 0	The solution must return false, because the indices must be distinct, so their absolute difference can never be zero.
The value of k is negative	The solution should return false, as the absolute difference between indices cannot be less than or equal to a negative number.
Array contains no duplicates at all	The solution will correctly iterate through the entire array and return false at the end.
Duplicates exist, but their index difference is greater than k	The solution correctly identifies the duplicates but returns false because the index distance condition is never met.
All elements in the array are identical	The solution should return true as long as k is 1 or greater and the array has at least two elements.
Large input array size with a large k	An efficient solution using a hash map or a sliding window with a set ensures linear time complexity, avoiding a timeout.

Empty input array

How to Handle:

The solution should return false immediately as no pairs of indices can be formed.

Array with a single element

How to Handle:

The solution should return false as there are no two distinct indices to compare.

The value of k is 0

How to Handle:

The solution must return false, because the indices must be distinct, so their absolute difference can never be zero.

The value of k is negative

How to Handle:

The solution should return false, as the absolute difference between indices cannot be less than or equal to a negative number.

Array contains no duplicates at all

How to Handle:

The solution will correctly iterate through the entire array and return false at the end.

Duplicates exist, but their index difference is greater than k

How to Handle:

The solution correctly identifies the duplicates but returns false because the index distance condition is never met.

All elements in the array are identical

How to Handle:

The solution should return true as long as k is 1 or greater and the array has at least two elements.

Large input array size with a large k

How to Handle:

An efficient solution using a hash map or a sliding window with a set ensures linear time complexity, avoiding a timeout.