An Interest In:
Web News this Week
- April 19, 2024
- April 18, 2024
- April 17, 2024
- April 16, 2024
- April 15, 2024
- April 14, 2024
- April 13, 2024
September 16, 2022 05:28 am GMT
Original Link: https://dev.to/uchihaitachi0/leetcode-217-contains-duplicate-dsa-4-592m
Leetcode 217. Contains Duplicate. DSA - 4
Question Link
Python || C++ || TypeScript
Brute Force Approach
This approach is very simple, so I am not going to waste much time in this approach
- We take one element and compare it with all the other elements.
- We do this for all the elements.
Code
def containsDuplicateMethod1(nums: list[int]) -> bool: length = len(nums) for i in range(length): for j in range(i + 1, length): if nums[i] == nums[j]: return True return False
Time Complexity: O(n^2)
Space Complexity: O(1)
Better Approach using Sorting
Since we have to find the duplicate elements, so we can sort the array and then find the duplicate elements.
Duplicate elements will be adjacent to each other.
For example: nums = [1, 2, 3, 1]
After sorting: nums = [1, 1, 2, 3]
Now we can find the duplicate elements by comparing the adjacent elements.
Code
def containsDuplicateMethod2(nums: list[int]) -> bool: nums.sort() length = len(nums) for i in range(length - 1): if nums[i] == nums[i + 1]: return True return False
Time Complexity: O(nlogn)
Space Complexity: O(1)
Best Approach using Hashing
This method is also very easy to understand.
- We create a Set.
- We traverse the array and check if the element is present in the Set or not.
- If the element is present in the Set then we return True.
- If the element is not present in the Set then we add the element in the Set.
- If we traverse the whole array, and we don't find any duplicate element then we return False.
Code
def containsDuplicateMethod3(nums: list[int]) -> bool: storage = set() for value in nums: if value in storage: return True storage.add(value) return False
Time Complexity: O(n)
Space Complexity: O(n)
Bonus
Best Approach using Hashing (one liner)
def containsDuplicateMethod4(nums: list[int]) -> bool: return len(nums) != len(set(nums))
Original Link: https://dev.to/uchihaitachi0/leetcode-217-contains-duplicate-dsa-4-592m
Share this article:
Tweet
View Full Article
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To