217. Contains Duplicate - Leetcode Easy

Problem statement

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

Approach 1 (Brute force)

Let's select an item in the array every time. Now, let's look at the remaining array to see if any other item with same value exists or not. If it exists, we return true. Else, false.

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

Time complexity: O(n^2) - due to nested for loops.
Space complexity: O(1)

Approach 2

If we sort the input array, all the duplicate elements are rearranged side by side. We can traverse through the array and keep checking the adjacent elements if they are same or not. If we find one such pair, we can return true.

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

        return False

Time complexity: O(n log n) - due to sorting.
Space complexity: O(1)

Approach 3

Let's iterate through the array and keep adding each item into a hashset. And before adding, check if that item is already present in that hashset. This checking operation takes O(1) time because it is a hashset. If we find one such element, we can return true.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        hashSet = set()
        for n in nums:
            if n in hashSet:
                return True
            else:
                hashSet.add(n)

        return False

Time complexity: O(n) - only one for loop.
Space complexity: O(n) - for extra hashset.

Conclusion

Do let me know if I missed any other approach.

Do follow me for more such explanations.
Let's connect on: Twitter LinkedIn Showwcase