217. Contains duplicate

217_solution1_hashset.c

#include <stdbool.h>
#include <stdlib.h>

typedef struct {
    int *slots;
    bool *used;
    int capacity;
} HashSet;

static HashSet hashset_create(int capacity) {
    HashSet set;
    set.capacity = capacity;
    set.slots = calloc(capacity, sizeof(int));
    set.used = calloc(capacity, sizeof(bool));
    return set;
}

static void hashset_free(HashSet *set) {
    free(set->slots);
    free(set->used);
}

static bool hashset_insert(HashSet *set, int value) {
    unsigned int idx = (unsigned int)value % set->capacity;

    while (set->used[idx]) {
        if (set->slots[idx] == value) {
            return false;
        }
        idx = (idx + 1) % set->capacity;
    }

    set->used[idx] = true;
    set->slots[idx] = value;
    return true;
}

bool containsDuplicate(int *nums, int numsSize) {
    if (numsSize == 0) {
        return false;
    }

    HashSet tracker = hashset_create(numsSize * 2);
    bool found = false;

    for (int i = 0; i < numsSize; i++) {
        if (!hashset_insert(&tracker, nums[i])) {
            found = true;
            break;
        }
    }

    hashset_free(&tracker);
    return found;
}

217_solution2_sorting.c

#include <stdbool.h>
#include <stdlib.h>

static int cmp(const void *a, const void *b) {
    return (*(const int *)a) - (*(const int *)b);
}

bool containsDuplicate(int *nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), cmp);

    for (int i = 1; i < numsSize; i++) {
        if (nums[i] == nums[i - 1]) {
            return true;
        }
    }

    return false;
}

217_solution3_optimized_hashset.c

#include <stdbool.h>
#include <stdlib.h>

typedef struct {
    int *slots;
    bool *used;
    int capacity;
} HashSet;

static HashSet hashset_create(int capacity) {
    HashSet set;
    set.capacity = capacity;
    set.slots = calloc(capacity, sizeof(int));
    set.used = calloc(capacity, sizeof(bool));
    return set;
}

static void hashset_free(HashSet *set) {
    free(set->slots);
    free(set->used);
}

static bool hashset_insert(HashSet *set, int value) {
    unsigned int idx = (unsigned int)value % set->capacity;

    while (set->used[idx]) {
        if (set->slots[idx] == value) {
            return false;
        }
        idx = (idx + 1) % set->capacity;
    }

    set->used[idx] = true;
    set->slots[idx] = value;
    return true;
}

bool containsDuplicate(int *nums, int numsSize) {
    if (numsSize == 0) {
        return false;
    }

    /* Larger load-factor headroom (4x) to cut probe-chain length vs solution1. */
    HashSet tracker = hashset_create(numsSize * 4);
    bool found = false;

    for (int i = 0; i < numsSize; i++) {
        if (!hashset_insert(&tracker, nums[i])) {
            found = true;
            break;
        }
    }

    hashset_free(&tracker);
    return found;
}

217_solution1_hashset.cpp

#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
  bool containsDuplicate(vector<int> &nums) {
    unordered_set<int> tracker;
    tracker.reserve(nums.size());

    for (int x : nums) {
      if (!tracker.insert(x).second)
        return true;
    }

    return false;
  }
};

217_solution2_sorting.cpp

#include <vector>
using namespace std;

class Solution {
public:
  bool containsDuplicate(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    for (int i = 1; i < nums.size(); i++) {
      if (nums[i] == nums[i - 1])
        return true;
    }
    return false;
  }
};

217_solution1_hashset.go

package solution

func containsDuplicate(nums []int) bool {
    tracker := make(map[int]struct{})

    for _, x := range nums {
        if _, ok := tracker[x]; ok {
            return true
        }
        tracker[x] = struct{}{}
    }

    return false
}

217_solution2_sorting.go

package solution

import "sort"

func containsDuplicate(nums []int) bool {
    sorted := make([]int, len(nums))
    copy(sorted, nums)
    sort.Ints(sorted)

    for i := 1; i < len(sorted); i++ {
        if sorted[i] == sorted[i-1] {
            return true
        }
    }

    return false
}

217_solution3_optimized_hashset.go

package solution

func containsDuplicate(nums []int) bool {
    tracker := make(map[int]struct{}, len(nums))

    for _, x := range nums {
        if _, ok := tracker[x]; ok {
            return true
        }
        tracker[x] = struct{}{}
    }

    return false
}

217_solution1_hashset.java

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> tracker = new HashSet<>();

        for (int x : nums) {
            if (!tracker.add(x)) {
                return true;
            }
        }

        return false;
    }
}

217_solution2_sorting.java

import java.util.Arrays;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        int[] sorted = nums.clone();
        Arrays.sort(sorted);

        for (int i = 1; i < sorted.length; i++) {
            if (sorted[i] == sorted[i - 1]) {
                return true;
            }
        }

        return false;
    }
}

217_solution3_optimized_hashset.java

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> tracker = new HashSet<>(nums.length * 2);

        for (int x : nums) {
            if (!tracker.add(x)) {
                return true;
            }
        }

        return false;
    }
}

217_solution1_hashset.js

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function (nums) {
  const tracker = new Set();

  for (const x of nums) {
    if (tracker.has(x)) {
      return true;
    }
    tracker.add(x);
  }

  return false;
};

217_solution2_sorting.js

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function (nums) {
  const sorted = [...nums].sort((a, b) => a - b);

  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i] === sorted[i - 1]) {
      return true;
    }
  }

  return false;
};

217_solution3_optimized_hashset.js

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function (nums) {
  return new Set(nums).size !== nums.length;
};

217_solution1_hashset.py

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

        for x in nums:
            if x in tracker:
                return True
            tracker.add(x)

        return False

217_solution2_sorting.py

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        sorted_nums = sorted(nums)

        for i in range(1, len(sorted_nums)):
            if sorted_nums[i] == sorted_nums[i - 1]:
                return True

        return False

217_solution3_optimized_hashset.py

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        return len(set(nums)) != len(nums)

217_solution1_hashset.rs

use std::collections::HashSet;

impl Solution {
    pub fn contains_duplicate(nums: Vec<i32>) -> bool {
        let mut tracker = HashSet::new();

        for x in nums {
            if !tracker.insert(x) {
                return true;
            }
        }

        false
    }
}

struct Solution;

217_solution2_sorting.rs

impl Solution {
    pub fn contains_duplicate(mut nums: Vec<i32>) -> bool {
        nums.sort();

        for i in 1..nums.len() {
            if nums[i] == nums[i - 1] {
                return true;
            }
        }

        false
    }
}

struct Solution;

217_solution3_optimized_hashset.rs

use std::collections::HashSet;

impl Solution {
    pub fn contains_duplicate(nums: Vec<i32>) -> bool {
        let mut tracker = HashSet::with_capacity(nums.len());

        for x in nums {
            if !tracker.insert(x) {
                return true;
            }
        }

        false
    }
}

struct Solution;