How to Solve the Contains Duplicate Problem in TypeScript

The Contains Duplicate problem is a popular algorithmic challenge where the goal is to determine if a list of numbers contains any duplicate elements. This problem tests your knowledge of basic data structures, array manipulation, and hash-based searching techniques.

In this post, we will explore multiple ways to solve this problem in TypeScript. We'll begin with a simple brute-force approach, then move on to a more optimized sorting-based solution, and finally discuss the most efficient approach using a Set.

Problem Definition

You are given an array of integers nums. The task is to determine if any value appears at least twice in the array. The function should return true if any value appears more than once, otherwise it should return false.

Example:

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

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

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

Constraints:

• The array size can range from 1 to (10^5).
• Each element can be as large as (10^9) or as small as (-10^9).

Let’s explore several ways to solve this problem in TypeScript.

Solution 1: Brute-Force Approach

Approach:

In the brute-force solution, we compare every element in the array with every other element. If we find two elements that are equal, we return true. If no duplicates are found by the end of all comparisons, we return false.

Code Implementation:

function containsDuplicate(nums: number[]): boolean {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] === nums[j]) {
                return true; // Duplicate found
            }
        }
    }
    return false; // No duplicates found
}

// Test the function
const nums = [1, 2, 3, 1];
console.log(containsDuplicate(nums));  // Output: true

Time and Space Complexity:

• Time Complexity: O(n²) due to two nested loops.
• Space Complexity: O(1) since we are not using any extra data structures.

Explanation:

This solution uses two loops: the outer loop picks an element, and the inner loop compares it to all elements that follow it. If we find two elements that are equal, the function immediately returns true. If no duplicates are found after all comparisons, it returns false.

Drawbacks:

This approach is inefficient for large arrays since its time complexity is O(n²). As the array grows in size, the time taken to complete the function increases dramatically, making it impractical for large datasets.

Solution 2: Sorting Approach

Approach:

A more efficient approach is to sort the array first. After sorting, any duplicate elements will appear next to each other. We can then simply check if any two consecutive elements are the same.

Code Implementation:

function containsDuplicate(nums: number[]): boolean {
    nums.sort((a, b) => a - b);  // Sort the array
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === nums[i - 1]) {  // Check consecutive elements
            return true;
        }
    }
    return false;
}

// Test the function
const nums = [1, 2, 3, 1];
console.log(containsDuplicate(nums));  // Output: true

Time and Space Complexity:

• Time Complexity: O(n log n) because sorting dominates the time complexity.
• Space Complexity: O(1) assuming the sorting is done in place.

Explanation:

This solution sorts the array using TypeScript’s built-in sort() function, which has a time complexity of O(n log n). After sorting, it checks adjacent elements to see if they are the same. If duplicates are found, the function returns true. If not, it returns false after the loop finishes.

Benefits and Drawbacks:

• Benefits: More efficient than the brute-force solution due to the reduced number of comparisons.
• Drawbacks: Sorting modifies the original array, and the time complexity is still O(n log n), which may not be ideal for very large datasets.

Solution 3: Using a Set (Optimal Solution)

Approach:

The most efficient way to solve this problem is by using a Set. A Set is a collection that stores unique values. As we iterate through the array, we can check if an element already exists in the set. If it does, we return true because that means a duplicate exists. Otherwise, we add the element to the set and continue.

Code Implementation:

function containsDuplicate(nums: number[]): boolean {
    const seen = new Set<number>();  // Create a new set to store unique elements
    for (const num of nums) {
        if (seen.has(num)) {  // If the element already exists in the set
            return true;
        }
        seen.add(num);  // Add the element to the set
    }
    return false;
}

// Test the function
const nums = [1, 2, 3, 1];
console.log(containsDuplicate(nums));  // Output: true

Time and Space Complexity:

• Time Complexity: O(n). We iterate through the array once, and both Set lookups and insertions are O(1) on average.
• Space Complexity: O(n) since we are using a set to store the elements.

Explanation:

This approach leverages the properties of a Set in TypeScript, where each element is stored only once, and lookups are very fast. For each element in the array, we check if it already exists in the set. If it does, the function returns true. If not, the element is added to the set, and the process continues. If no duplicates are found, the function returns false.

Benefits and Drawbacks:

• Benefits: This is the most efficient solution in terms of time complexity, offering O(n) performance.
• Drawbacks: The only downside is the extra space required to store the set, which is O(n). However, this is usually a reasonable trade-off for the speed gained.

Edge Cases

When solving the Contains Duplicate problem in TypeScript, it is crucial to handle various edge cases to ensure the solution works in all scenarios. Below are some important edge cases that should be considered when implementing the solution:

1. Empty Array:

If the input array is empty, there are no elements to compare, so the function should return false.

Example:

const nums: number[] = [];
console.log(containsDuplicate(nums));  // Output: false

• Expected Output: Since there are no elements in the array, there cannot be any duplicates, so the function should return false.

2. Array with One Element:

If the array contains only one element, it is impossible to have duplicates, so the function should return false.

Example:

const nums = [1];
console.log(containsDuplicate(nums));  // Output: false

• Expected Output: Since there is only one element, it cannot have duplicates, so the function should return false.

3. Array with All Unique Elements:

If the input array contains all unique elements (i.e., no duplicates), the function should return false.

Example:

const nums = [1, 2, 3, 4, 5];
console.log(containsDuplicate(nums));  // Output: false

• Expected Output: Since all elements in the array are unique, the function should return false.

4. Array with All Duplicate Elements:

If the array consists entirely of the same element repeated multiple times, the function should return true.

Example:

const nums = [1, 1, 1, 1];
console.log(containsDuplicate(nums));  // Output: true

• Expected Output: Since every element in the array is the same, the function should return true.

5. Array with Negative Numbers:

The array may contain negative numbers. The solution should correctly handle and identify duplicates among negative numbers.

Example:

const nums = [-1, -2, -3, -1];
console.log(containsDuplicate(nums));  // Output: true

• Expected Output: The element -1 appears twice, so the function should return true.

6. Array with Negative and Positive Numbers:

The array may contain both negative and positive numbers. The solution should distinguish between these correctly.

Example:

const nums = [-1, 2, -3, 3];
console.log(containsDuplicate(nums));  // Output: false

• Expected Output: Since all elements are unique, the function should return false.

7. Array with Zeros:

The array may contain zero values, and the solution should handle multiple zeros correctly.

Example:

const nums = [0, 1, 2, 0];
console.log(containsDuplicate(nums));  // Output: true

• Expected Output: The element 0 appears twice, so the function should return true.

8. Array with Mixed Duplicates and Unique Elements:

The array may contain a mix of unique and duplicate elements. The function should return true as soon as a duplicate is found.

Example:

const nums = [1, 2, 3, 2];
console.log(containsDuplicate(nums));  // Output: true

• Expected Output: The element 2 appears twice, so the function should return true.

9. Array with Large Numbers:

The array may contain very large or very small integers within the range [-10^9, 10^9]. The solution should handle these extreme values correctly.

Example:

const nums = [-1000000000, 1000000000];
console.log(containsDuplicate(nums));  // Output: false

• Expected Output: Since the two elements are different and within the valid range, the function should return false.

10. Array with Maximum Length (100,000 elements):

If the array contains the maximum number of elements (100,000), the solution should handle the large dataset efficiently. This is especially important for the brute-force solution, which may fail or run too slowly for such input sizes.

Example:

const nums = Array.from({ length: 100000 }, (_, i) => i);
nums[99999] = 99998;  // Add a duplicate
console.log(containsDuplicate(nums));  // Output: true

• Expected Output: The array contains a duplicate at the last position, so the function should return true. The solution should handle the large input size efficiently.

Conclusion

In this post, we explored three different solutions for solving the Contains Duplicate problem in TypeScript:

1. Brute-force approach: A simple but inefficient solution with O(n²) time complexity.
2. Sorting approach: A faster solution with O(n log n) time complexity, but it modifies the original array.
3. Set approach: The optimal solution with O(n) time complexity and O(n) space complexity, making it the best choice for large datasets.

When facing this problem in practice, the set-based solution should be your go-to method due to its efficiency in terms of both speed and ease of implementation.