Contains Duplicate
In this blog, we will discuss the "Contains Duplicate" problem, which is a popular problem in coding interviews. We will go through the problem statement, explain the approach, and provide both brute force and optimal solutions. Additionally, we will perform a dry run of the code for better understanding and analyze the time and space complexity of each solution.
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.
Examples
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 <= 105
-109 <= nums[i] <= 109
Brute Force Solution
Algorithm
The simplest way to solve this problem is by comparing each element with every other element in the array. If any two elements are the same, we return true. If no duplicates are found after all comparisons, we return false.
Pseudocode
for i from 0 to nums.length - 1:
for j from i + 1 to nums.length - 1:
if nums[i] == nums[j]:
return true
return false
Explanation
This approach involves a nested loop where each element is compared with every other element. If a duplicate is found, the function immediately returns true. If the loops complete without finding a duplicate, the function returns false.
Java Code
package codeKatha;
public class ContainsDuplicate {
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;
}
}
Dry Run
Let's consider the example nums = [1,2,3,1]:
i = 0, nums[i] = 1
j = 1, nums[j] = 2 (1 != 2)
j = 2, nums[j] = 3 (1 != 3)
j = 3, nums[j] = 1 (1 == 1) -> return true
Time and Space Complexity
Time Complexity: O(n2) because we have a nested loop iterating over the array.
Space Complexity: O(1) as we are not using any extra space except for variables.
Optimal Solution Using HashSet
Algorithm
We can use a HashSet to achieve a more optimal solution. A HashSet stores only unique elements. As we iterate through the array, we add elements to the HashSet. If we encounter an element that is already in the HashSet, we return true. If we complete the loop without finding duplicates, we return false.
Pseudocode
initialize an empty set called seen
for each element num in nums:
if num is in seen:
return true
add num to seen
return false
Explanation
This approach uses the properties of a HashSet, which allows us to check for duplicates in constant time, making it much more efficient than the brute force approach.
Java Code
package codeKatha;
import java.util.HashSet;
public class ContainsDuplicate {
public boolean containsDuplicate(int[] nums) {
HashSet<Integer> seen = new HashSet<>();
for (int num : nums) {
if (seen.contains(num)) {
return true;
}
seen.add(num);
}
return false;
}
}
Dry Run
Let's consider the example nums = [1,2,3,1]:
seen = {}
num = 1, seen = {1}
num = 2, seen = {1, 2}
num = 3, seen = {1, 2, 3}
num = 1, 1 is already in seen -> return true
Time and Space Complexity
Time Complexity: O(n) because we are iterating through the array once.
Space Complexity: O(n) as we are using a HashSet to store unique elements.
Sorting Solution
Algorithm
Another way to solve the problem is by sorting the array first and then checking for consecutive duplicates. If any two consecutive elements are the same, return true. Otherwise, return false.
Pseudocode
sort nums
for i from 1 to nums.length - 1:
if nums[i] == nums[i - 1]:
return true
return false
Explanation
Sorting the array places any duplicate elements next to each other, allowing us to check for duplicates with a single pass through the array.
Java Code
package codeKatha;
import java.util.Arrays;
public class ContainsDuplicate {
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
return true;
}
}
return false;
}
}
Dry Run
Let's consider the example nums = [1,2,3,1]:
sorted nums = [1,1,2,3] i = 1, nums[1] = 1, nums[0] = 1 -> return true
Time and Space Complexity
Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(1) for in-place sorting, O(n) if sorting creates a new array.
Edge Cases
Let's consider some edge cases:
- If the array is empty or has only one element, return
falseas there can be no duplicates. - If all elements are the same, the function should return
true. - If the array contains maximum constraints like very large integers, ensure the solution handles them efficiently.
Conclusion
We discussed multiple approaches to solving the "Contains Duplicate" problem, starting from the brute force method to more optimized solutions using HashSet and sorting. Understanding the time and space complexity helps in selecting the best approach depending on the input size and constraints.
Feel free to try these methods and choose the one that best fits your use case.
Comments
Post a Comment