Contains Duplicate

Patrick Leaton

Published: March 5, 2021, 8:31 p.m.

Problem Description

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.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

The description was taken from https://leetcode.com/problems/contains-duplicate/.

Problem Solution

#O(N) Time, O(N) Space

class Solution:

def containsDuplicate(self, nums: List[int]) -> bool:

seen = {}

for num in nums:

if num in seen:

return True

else:

seen[num] = 'Seen'

return False

Problem Explanation

This is one of those questions that rely on knowing where other elements are in a list. If the list was sorted, then we would just need to check neighboring duplicates. If the input of numbers and the length of the array ranged from one to n then we would be able to utilize Floyd's Tortoise and Hare algorithm or we would be able to iterate through the array and mark the index correlated to the element we see as negative, then the second time we mark the same index as negative then we would have found a duplicate. Since it is not sorted, and the input does not range from one to n, we are going to need some external memory. Here we will use a hashmap.

We can iterate through the array, marking each value as seen by adding it to the hashmap, and if the current value we are at is already in hashmap, we will return true. Otherwise, we will return false.

We will start off by initializing our seen dictionary.

seen = {}

Afterward, we will iterate through the input array and check if the number we're currently looking at is already in the dictionary.

We will return true if it is since we have a duplicate.