Design Gurus Logo
Blind 75
Solution: Contains Duplicate

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.

Brute force approach to solve Contains Duplicate
Brute force approach to solve Contains Duplicate

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 named unique_set is created to store unique elements.

  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 unique_set.

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

    • If "x" is not in the unique_set, then the algorithm adds "x" to the unique_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:

Image

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), where N is the number of elements in the array.

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).

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)