Contains Duplicate

Difficulty: #easy

This is based off of the problem found on leetcode called (Contains Duplicate).

Has the following problem text,

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.

Solutions

Optimal solution

The most efficient solution (in terms of time) would be to use an hashset and to keep comparing the contents of that with new elements. This would be a $o(n)$ time complexity, as well as space complexity.

An example implementation in python,

from typing import List


class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        hashset = set()

        for n in nums:
            if n in hashset:
                return True
            hashset.add(n)
        return False

Less space complexity, slower solution

You could also sort your input, and then compare each next element - this would give you a linear time complexity ($o(n)$) and no additional space complexity (assuming your sort doesn’t require additional space, and you sort your input in-place). The cost of sorting would be less ($O(n\space log\space n)$) than linear time.

An example implementation in python,

from typing import List


class Solution:
    def containsDuplicateSortVersion(self, nums: List[int]) -> bool:
        # Sorting in place.
        nums.sort()
        for i in range(len(nums) - 1):
            if nums[i] == nums[i+1]:
                return True
        return False

Brute force solution

And there is, of course, the brute force approach that would have a complexity of $O(n^2)$ as you would have to iterate over each element, and compare that element with each other element.

An example implementation in python,

from typing import List


class Solution:
    def containsDuplicateBruteForceVersion(self, nums: List[int]) -> bool:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] == nums[j]:
                    return True
        return False

Hashset solution in Golang with tests

This is an example implementation in Golang, using the hashset version of the solution,

solution.go

package main

func containsDuplicates(input []int) bool {
	hashset := make(map[int]bool)

	for _, n := range input {
		if _, exists := hashset[n]; exists {
			return true
		}
		hashset[n] = true
	}

	return false
}

solution_test.go

package main

import (
	"testing"
)

func generateLargeInput(size int) []int {
	input := make([]int, size)
	for i := 0; i < size; i++ {
		input[i] = i
	}
	input[size-1] = 0 // Add a duplicate
	return input
}

func TestContainsDuplicates(t *testing.T) {
	tests := []struct {
		name     string
		input    []int
		expected bool
	}{
		{"empty list", []int{}, false},
		{"single element", []int{1}, false},
		{"duplicate elements", []int{1, 2, 3, 1}, true},
		{"all unique elements", []int{1, 2, 3, 4, 5}, false},
		{"duplicate elements with duplicates", []int{1, 2, 3, 1, 2}, true},
		{"large input", generateLargeInput(10000), true},
	}

	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			if got := containsDuplicates(tt.input); got != tt.expected {
				t.Errorf("containsDuplicates(%v) = %v, want %v", tt.input, got, tt.expected)
			}
		})
	}
}

You can run the above with go test assuming you’ve created a go module, and have two separate files, solution.go, and solution_test.go.