ntree.ai
ntree.aiContains Duplicate

Solutions

1. Brute Force

O(n²) time | O(1) space

Intuition

We can check every possible pair of numbers in the array and return true as soon as any pair is equal.

Algorithm

  1. Iterate through the outer loop from the first element to the last element with i index.
  2. For each outer loop iteration, iterate through the inner loop from the element at i + 1 to the last element with j index.
  3. Return true if the element at i is equal to the element at j.
  4. Return false when both loops finish.
4
7
1
9
7
01234
i j
4 ≠ 7
1 / 8

Code

Code
Python
def containsDuplicate(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
/**
 * @param {number[]} nums
 * @returns {boolean}
 */
var containsDuplicate = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] === nums[j]) return true
    }
  }
  return false
}
class Solution {
    public boolean containsDuplicate(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) return true;
            }
        }
        return false;
    }
}

2. Sorting

O(nlogn) time | O(1) space

Intuition

If we sort the array first, all the equal elements will be positioned next to each other.

So we can compare every element only with the next one to check if a duplicate exists.

Algorithm

  1. Sort the array.
  2. Iterate through the loop from the first element to the second to last element with i index.
  3. Return true if the element at i is equal to the element at i + 1.
  4. Return false when the loop finishes.
4
7
1
9
7
01234
Sort the array
1 / 5

Code

Code
Python
def containsDuplicate(nums: list[int]) -> bool:
    nums.sort()
    for i in range(len(nums) - 1):
        if nums[i] == nums[i + 1]:
            return True
    return False
/**
 * @param {number[]} nums
 * @returns {boolean}
 */
var containsDuplicate = function (nums) {
  nums.sort((a, b) => a - b)
  for (let i = 0; i < nums.length - 1; i++) {
    if (nums[i] === nums[i + 1]) return true
  }
  return false
}
import java.util.Arrays;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) return true;
        }
        return false;
    }
}

3. Hash Table

O(n) time | O(n) space

Intuition

We can use a hash set to check if an element is a duplicate.

Algorithm

  1. Create an empty hash set.
  2. Iterate through the loop from the first element to the last element.
    • If the element is in the hash set, return true.
    • Otherwise add the element to the hash set.
  3. Return false when the loop finishes.
4
7
1
9
7
01234
4 is not in the hash set
1 / 6

Code

Code
Python
def containsDuplicate(nums: list[int]) -> bool:
    seen = set()
    for n in nums:
        if n in seen:
            return True
        seen.add(n)
    return False
/**
 * @param {number[]} nums
 * @returns {boolean}
 */
var containsDuplicate = function (nums) {
  const seen = new Set()
  for (const n of nums) {
    if (seen.has(n)) return true
    seen.add(n)
  }
  return false
}
import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int n : nums) {
            if (seen.contains(n)) return true;
            seen.add(n);
        }
        return false;
    }
}
def containsDuplicate(nums: list[int]) -> bool:
    pass
 

Press Visualise to step through your code.