HashSet provides constant average time complexity for insertion and lookup. Instead of comparing every pair of elements, store each visited element in the HashSet. If an element already exists in the set, a duplicate has been found immediately. This reduces the time complexity from O(n²) to O(n).
Problem stats
Before
Compare every element with every other element.
For each index:
1. Compare the current element with all remaining elements.
2. If any duplicate is found, return true.
3. If no duplicate exists after checking all pairs, return false.
This approach is simple but inefficient because it uses nested loops.
After
Use a HashSet to keep track of visited elements.
Traverse the array:
1. If the current element already exists in the HashSet, return true.
2. Otherwise, add the element to the HashSet.
3. If the traversal completes without finding duplicates, return false.
This approach performs only one traversal of the array.
The optimized implementation, ready for interview preparation and quick revision.
Solution.java
1import java.util.HashSet;2import java.util.Set;3 4public class Solution {5 6 public boolean containsDuplicate(int[] nums) {7 8 Set<Integer> seen = new HashSet<>();9 10 for (int num : nums) {11 12 if (seen.contains(num)) {13 return true;14 }15 16 seen.add(num);17 }18 19 return false;20 }21 22 public static void main(String[] args) {23 24 Solution solution = new Solution();25 26 int[] nums = {1, 2, 3, 1};27 28 System.out.println(solution.containsDuplicate(nums));29 }30}Analyze the efficiency of the algorithm by understanding its time and space complexity across different execution scenarios.
Time complexity
Space complexity
By execution case
Best case
O(n)
Average case
O(n)
Worst case
O(n)
This solution achieves a O(n) time complexity while using O(n) extra memory. It is considered the optimal approach for this problem and is suitable for coding interviews as well as competitive programming.
Every coding problem teaches a pattern. Focus on the concepts, avoid common mistakes, and remember the interview-worthy takeaways instead of memorizing code.
The biggest takeaway from this problem.
HashSet provides constant average time complexity for insertion and lookup. Instead of comparing every pair of elements, store each visited element in the HashSet. If an element already exists in the set, a duplicate has been found immediately. This reduces the time complexity from O(n²) to O(n).
Explain why the optimized solution works before writing the final code. Interviewers care about your thinking process as much as your implementation.
Avoid jumping directly to coding. Always analyze edge cases, constraints, and the optimal approach before implementation.
Focus on understanding the algorithm's pattern instead of memorizing the code. Once the logic becomes clear, implementing the solution in any programming language becomes much easier.
Every DSA problem introduces a reusable pattern. Instead of remembering the exact solution, remember the thought process that led to it. Over time, these patterns will help you solve new problems much faster and perform better in coding interviews.
Practice consistently and move through the roadmap one problem at a time.
Previous
Search in Rotated Sorted Array
Practice similar problems to strengthen your understanding of the underlying algorithm and improve pattern recognition.