Efficient Java Solution for LeetCode 217 - Contains Duplicate

In the world of competitive programming and technical interviews, problem-solving skills are essential. One of the most common problems asked in coding interviews is detecting duplicates in an array, often appearing under array manipulation topics. Today, I’ll walk you through my efficient solution to LeetCode problem 217: Contains Duplicate, optimized with a 10ms runtime that beats 89.42% of submissions.

Problem Statement

The task is simple: given an integer array nums, determine if any value appears at least twice in the array. If any value appears more than once, return true; otherwise, return false.

Approach & Solution

To solve this problem, the most efficient approach leverages the HashSet data structure in Java. A HashSet allows us to store unique elements only and provides a constant-time complexity O(1) for lookups and insertions. This makes it ideal for solving problems that involve detecting duplicates efficiently.

Step-by-Step Breakdown:

Initialize a HashSet: Start by creating an empty HashSet to store unique elements as we iterate through the array.

• Iterate Through the Array: For each element in the array, check if it's already in the HashSet.
• If it exists in the set, return true immediately, as it means a duplicate is found. Otherwise, add the element to the set.
• Return false: If no duplicates are found after iterating through the array, return false.

This approach ensures that we only make one pass through the array, giving us a time complexity of O(n), where n is the number of elements in the array. Since we use extra space to store the set, the space complexity is O(n) as well.

import java.util.HashSet;

import java.util.Set;

public class ContainsDuplicate {

public static void main(String[] args) {

int[] nums = {1,2,1,4,6,2};

System.out.println("nums contain duplicate: "

                                                   +containsDuplicate(nums));

}

public static boolean containsDuplicate(int[] nums) {

Set<Integer> l = new HashSet<>();

for(int i: nums){

if(l.contains(i)){

return true;

} else {

l.add(i);

}

}

return false;

}

}

Why This Approach?

1. Efficiency: By using a HashSet, we reduce the time complexity for checking duplicates
   to O(1), instead of using nested loops that would result in O(n²) time complexity.
2. Clarity: The solution is simple and easy to understand, making it easier to maintain and explain in an interview setting.
3. Scalability: The approach scales well for large datasets, providing quick results
   even when dealing with large input arrays.

Performance

After implementing this solution, I achieved a runtime of 10ms on LeetCode, outperforming 89.42% of other submissions. In terms of memory usage, it was optimized to 57.63 MB, beating 64.44% of submissions.

Conclusion

This problem is a great example of how using the right data structures can drastically improve performance. It reinforces the importance of understanding time and space complexity, especially for coding interviews. If you’re preparing for a technical interview or just looking to improve your data structure skills, mastering problems like 217: Contains Duplicate is key. 

Tags: #LeetCode #Java #ContainsDuplicate #CodingInterview #DSA #HashSet #ArrayManipulation #CodingChallenges #InterviewPrep