Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Contains Duplicate

Problem Statement

Examples

Solution

Approach 1: Brute Force

Approach 2: Using Hash Set

Approach 3: Sorting

Which approach to give in an interview

Problem Statement

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Examples

Example 1:

Input: nums= [1, 2, 3, 4]
Output: false  
Explanation: There are no duplicates in the given array.

Example 2:

Input: nums= [1, 2, 3, 1]
Output: true  
Explanation: '1' is repeating.

Example 3:

Input: nums= [3, 2, 6, -1, 2, 1]
Output: true  
Explanation: '2' is repeating.

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

Solution

Approach 1: Brute Force

We can use a brute force approach and compare each element with all other elements in the array. If any two elements are the same, we'll return true. If we've gone through the entire array and haven't found any duplicates, we'll return false.

Here is the nested loop running on [3, 2, 6, -1, 2, 1]. Move through the steps one at a time:

mediaLink

Step 1. The array is [3, 2, 6, -1, 2, 1]. The brute force approach fixes one position i and compares it against every position to its right, then moves i along. The moment two values match, the answer is true and the scan can stop.

1 of 4

Code

Here is the code for this algorithm:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Outer loop: The outer loop runs N times, where N is the length of the input array. This gives the outer loop a time complexity of O(N).
  • Inner loop (nested): For each iteration of the outer loop, the inner loop runs N - i - 1 times, which decreases as i increases. In the worst case, the inner loop will run approximately N times for the first element, N - 1 times for the second element, and so on. This results in a total time complexity for the inner loop of O(N^2).

Overall time complexity: O(N^2).

Space Complexity

  • The algorithm only uses a few variables (i, j, and boolean result), all of which require constant space.
  • No additional data structures are used that depend on the input size.

Overall space complexity: O(1).

Approach 2: Using Hash Set

We can use the set data structure to check for duplicates in an array.

Since a set can only hold unique elements, we can check if the elements in the given array are present more than once by adding them to a set. This way, we can determine if there are any duplicates in the array.

This approach works as follows:

  1. A set is created to store the values we have already seen.

  2. The algorithm then iterates through the input array nums.

  3. For each element "x" in the array, the algorithm checks if "x" is already in the set.

    • If "x" is in the set, then the algorithm returns True, indicating that a duplicate has been found.

    • If "x" is not in the set, then the algorithm adds "x" to the set.

  4. The iteration continues until all elements in the array have been processed.

  5. If no duplicates are found, the algorithm returns False.

This approach utilizes the property of sets to store only unique elements, making it an efficient solution for finding duplicates in an array.

Here is the algorithm Walkthrough:

mediaLink

3 is not in the set yet, so it is added

1 of 6

Code

Here is the code for this algorithm:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Loop through the array: The algorithm iterates over the array nums once. This gives a time complexity of O(N), where N is the number of elements in the array.
  • HashSet operations: For each element, the algorithm performs a HashSet.add() operation. On average, adding or checking elements in a HashSet has a time complexity of O(1) due to its underlying hash table structure.

Overall time complexity: O(N) on average, where N is the number of elements in the array. In the worst case, when every element lands in the same hash bucket, it is O(N^2).

Space Complexity

  • HashSet storage: The algorithm uses a HashSet to store unique elements. In the worst case, when all elements are unique, the HashSet will contain N elements.
  • This results in a space complexity of O(N), where N is the number of unique elements in the array.

Overall space complexity: O(N).

A shorter variant, and what it costs. Many people reach for a one-liner here: build a set from the whole array and compare its size with the array length.

return len(set(nums)) != len(nums)

It is correct, and it is the same O(N) time and O(N) space. What it gives up is the early return. The loop above stops the moment it sees a repeat, so on [1, 1, ...] with a million elements it reads two of them. The one-liner always builds the whole set first, so it reads all million. Same complexity, different work on the inputs that repeat early.

Both are fine answers in an interview. Say the one-liner, then mention that the explicit loop can exit early, and you have shown you know the difference rather than just the shorter syntax.

Approach 3: Sorting

Another approach is to sort the array first and then check for duplicates.

We'll sort the array and then iterate through it, comparing each element with the next one.

If any two elements are the same, we'll return true. If we've gone through the entire array and haven't found any duplicates, we'll return false.

Code

Here is the code for this algorithm:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • The algorithm first sorts the array using Arrays.sort(), which has a time complexity of O(N \log N), where N is the number of elements in the array.
  • After sorting, the algorithm performs a single pass through the array to compare adjacent elements. This step takes O(N) time.
  • Therefore, the overall time complexity is dominated by the sorting operation, making it O(N \log N).

Space Complexity

  • The space complexity of the sorting algorithm depends on the implementation of Arrays.sort(). In the case of primitive types like int[], it uses a variant of the quicksort algorithm, which has a space complexity of O(\log N) due to the recursion stack for in-place sorting.
  • The algorithm itself only uses a constant amount of extra space for the index variable and the loop, which does not depend on the size of the input.

Thus, the overall complexity is:

  • Time Complexity: O(N \log N)
  • Space Complexity: O(\log N)

Which approach to give in an interview

Approach 2, the hash set, is the one to give. It runs in O(N) time in a single pass, and it is the shortest to write correctly under pressure. Use approach 3, sorting, only when memory is tight. It trades O(N) time for O(N \log N) and drops the extra memory to whatever the sort itself needs, which is O(\log N) for a typical library sort rather than O(1). If the requirement is strictly constant extra space, name an in-place sort such as heapsort, because most library sorts are not in place: Python's Timsort can allocate O(N). Approach 1 is here to show why the other two exist, not as an answer to offer.

Shubham Pokale

Shubham Pokale

· 5 days ago

   for i in range(len(nums)):
            if nums[i] in nums[i+1:]:
                return True
       
Show 1 reply
Shubham Pokale

Shubham Pokale

· 5 days ago

Are we using set because we need fast membership checking. A set uses hashing and provides O(1) average-time lookup, whereas searching for an element in a list takes O(n). Therefore, the set solution runs in O(n) overall instead of O(n²).

Show 1 reply
Shivam Badal

Shivam Badal

· 11 days ago

I did this at first, but when looking at the solution I saw the point of the exercise.

sset = set(nums)
return False if len(sset) == len(nums) else True
Show 1 reply
Raúl Fiol

Raúl Fiol

· a year ago

I just found another solution using Set(): by copying each element into a new set. Since a set only stores distinct elements, if the number of elements in the input matches the size of the Set, it means there are no duplicates

function containsDuplicate(nums) {
    if(!nums || nums.length == 0){
      return false;
    }
    
    let nums_copy = new Set();

    for(let i = 0; i<nums.length;i++){
      nums_copy.add(nums[i]);
    }

    return nums_copy.size == nums.length ? false:true;
  }
Show 2 replies
mil o

mil o

· 2 years ago

Is there a reason why this would not be a good solution? Maybe I am overlooking something here

const uniqueSet = new Set(nums);

if (uniqueSet.size !== nums.length) {
	return true; 
}
Show 6 replies
Jeana

Jeana

· 2 years ago

The problem didnt call for an item not found in the set to be added into the set.

The problem simply states to return if the set contains duplicates or not. This is very weird to me.

Show 2 replies
Zachary Nelson

Zachary Nelson

· 2 years ago

I appreciate that 3 example solutions are given but they are not given in order from least to most optimal. It would be nice to at least callout which solution for problems is the most optimal solution.

raol buqi

raol buqi

· 2 years ago

in the article you wrote set.count(x), set doesn't have a count method

Show 2 replies
Abhijit Gupta

Abhijit Gupta

· 2 years ago

The count operation on a HashSet does not make sense. Please check this line -

set.count(x) also has an average time complexity of O(1)."

Show 1 reply
Anonymous

Anonymous

· 2 years ago

I'm confused why would the worst case scenario for approach 2 be O(n^2) when using a Set in JavaScript since if the number already exists in the set, the add operation would just be ignored and the code would just early return true? So shouldn't the worst case scenario for approach 2 still be O(n)?

Show 2 replies

Reading Progress

0%

Vote for new content

On This Page

Problem Statement

Examples

Solution

Approach 1: Brute Force

Approach 2: Using Hash Set

Approach 3: Sorting

Which approach to give in an interview