Contains Duplicate
Problem Statement
Given an array of integers nums as input, implement a function containsDuplicate such that it returns true if nums contains a duplicate value and false otherwise.
Input Constraints: Values in nums could range from 1 to 105
Output Constraints: Could be either true or false
Naive Approach to Solution
We can loop over the array to select a value from nums and find its duplicate in the rest of the array by executing a nested loop.
func containsDuplicate(nums):
for index1 in range(0, nums):
for index2 in range(index1+1, nums):
if nums[index1] == nums[index2]:
return true
return false
Time Complexity in the worst case scenario: O(n2), because we are performing nested iterations over nums.
Space Complexity in the worst case scenario: O(1), because we are not using any additional memory while executing this solution.
Optimized Approach to Solution
Nested loops are the major contributor to the time complexity of the naive solution. We executed a second loop in order to search for the duplicate in the nums, but what if we had a data structure that could tell us if an element is present in nums (or not) without iterating over the complete array?
We can use a hashmap to store the elements in nums that we have encountered during the iteration and validate against that while checking for duplicates.
func containsDuplicate(nums):
hm := Hashmap()
for val in nums:
if val in hm:
return true
else:
hm[val] = 1
Since the purpose of the hashmap is to check if an element is present in nums or not, the value in key-value pair of the hashmap does not matter (we are using 1 in this case but it could be substituted with anything).
Time Complexity in the worst case scenario: O(n), because we only need a single iteration over the nums to check for duplicates in the hashmap and update the hashmap with each non-duplicate value encountered.
Space Complexity in the worst case scenario: O(n), because for certain inputs we could have to store all the elements in nums until we encounter a duplicate at the last element.
Solution Code (Go)
func containsDuplicate(nums []int) bool {
hm := make(map[int]int)
for _, n := range nums {
_, found := hm[n]
if found {
return true
}
hm[n] = 1
}
return false
}
Pattern recognition
If you encounter a problem where you have to perform multiple checks for a value in an array or string. Then an optimized approach will be, to store the values from that array or string in a hashmap. It will reduce the time complexity to check for a value from O(n) (by looping over all the values/characters in a array/string) to O(1).