Contains Duplicate in Java DSA: Brute Force, Sorting, and the HashSet Trick

Learn the Contains Duplicate in Java DSA problem the easy way. Compare brute force, sorting, and the fast HashSet approach with a clear beginner dry run.

1. Introduction

Contains Duplicate in Java is one of those warm-up questions you meet early in any array series. It looks almost too simple. But it quietly teaches you how a HashSet works, and that lesson shows up again and again in harder problems.

Here is the task in plain words. You get an array of numbers. You must answer one yes-or-no question: Does any value appear more than once? If even a single number repeats, you return true. If every number is unique, you return false.

In this guide, we build up slowly. First, we try the obvious brute force. Then we speed it up with sorting. Finally, we reach the clean HashSet solution that most interviewers want to see. Along the way, we dry-run the code by hand, so you can watch it work step by step.

2. Understanding the Problem

Let us lock down the rules before we write any code. A clear problem statement saves you from silly bugs.

• You get an array of integers, for example [1, 2, 3, 1].
• Your job is to return true if any value appears at least twice.
• You return false only when every single value is unique.
• The array can be empty or hold just one number. Both cases have no duplicate.

So for [1, 2, 3, 1] the answer is true, because 1 shows up at index 0 and again at index 3. For [1, 2, 3, 4] the answer is false, since nothing repeats. Notice we return a boolean here, not an index. Beginners sometimes overthink this and start hunting for positions.

3. Concepts You Need Here

Before the code, let us name the two ideas that carry this whole problem. Both are small, and you will lean on them in many array questions later.

3.1 The HashSet

A HashSet stores unique values and answers one question fast: is this value already inside? On average, that check takes constant time. So you skip scanning the array again and again. Instead, you keep a running memory of what you have seen, and you just ask the set.

3.2 Sorting for Adjacency

The second idea is simpler. When you sort an array, equal values end up sitting next to each other. So a duplicate is never far away; it is always the neighbor. That turns a wide search into a quick side-by-side check.

4. Approach 1: Brute Force

The first idea most people reach for is simple. Compare every number with every other number. If any two match, you found a duplicate.

4.1 Pseudocode

for i from 0 to n-1:
    for j from i+1 to n-1:
        if nums[i] == nums[j]:
            return true
return false   // no duplicate found

The outer loop picks one number. The inner loop checks it against every later number. We start j at i plus 1, so we never compare a number with itself. This also avoids checking the same pair twice.

4.2 Java Code

public class ContainsDuplicateBrute {
    public static 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;
    }
 
    public static void main(String[] args) {
        int[] nums = { 1, 2, 3, 1 };
        System.out.println(containsDuplicate(nums)); // true
    }
}

4.3 Why This Works, Step by Step

Let us walk through the code slowly. Each line has one clear job.

• The outer variable i points at the first number in a pair.
• The inner variable j points at a number after i, so we test i against every later value.
• Inside, we compare nums[i] with nums[j]. A match means we found a repeat.
• The moment we spot a match, we return true right away and stop early.
• If both loops finish with no match, we return false.

This code is easy to read and hard to get wrong. That is its strength. The weakness is speed, which we fix next.

4.4 Time and Space Cost

Brute force checks almost every pair. For an array of size n, that is roughly n times n over two comparisons. So the time is O(n squared). The space stays O(1), because we only use a couple of loop variables. For small arrays, this is fine. For large ones, it drags.

5. Approach 2: Sorting First

Here is a neat middle-ground idea. If you sort the array, then any duplicate values sit right next to each other. So you only need to check each number against its neighbor.

5.1 Pseudocode

sort(nums)
for i from 1 to n-1:
    if nums[i] == nums[i-1]:
        return true
return false

5.2 Java Code

import java.util.Arrays;
 
public class ContainsDuplicateSort {
    public static 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;
    }
 
    public static void main(String[] args) {
        int[] nums = { 1, 2, 3, 1 };
        System.out.println(containsDuplicate(nums)); // true
    }
}

5.3 Reading the Code

• First we call Arrays.sort(nums), which reorders the values from smallest to largest.
• Then we loop from index 1 and compare each number with the one just before it.
• Because duplicates now sit side by side, one neighbor check is enough to catch them.

Sorting takes O(n log n) time, which beats brute-force on large inputs. The catch is that Arrays.sort changes the original order of your array. If the caller still needs the original order, this approach can surprise them.

6. Approach 3: The HashSet Trick

Now for the version interviewers really want. The idea is to remember every number as you walk the array once. Before you store a number, you first ask a simple question: Have I seen this value already?

If the value is already in your memory, you found a duplicate and return true. If not, you add it and move on. A HashSet is perfect here, because it checks membership in constant time on average.

6.1 Pseudocode

seen = empty set
for each num in nums:
    if num is in seen:
        return true
    add num to seen
return false

6.2 Java Code

import java.util.HashSet;
 
public class ContainsDuplicateHashSet {
    public static boolean containsDuplicate(int[] nums) {
        HashSet<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (seen.contains(num)) {
                return true;
            }
            seen.add(num);
        }
        return false;
    }
 
    public static void main(String[] args) {
        int[] nums = { 1, 2, 3, 1 };
        System.out.println(containsDuplicate(nums)); // true
    }
}

6.3 Reading the Code Line by Line

This version does the most thinking, so let us break it down gently.

• We create a HashSet called seen. It holds every value we have looked at so far.
• We loop once through the array. There is no inner loop, which is the whole point.
• For each number, we call seen.contains(num). If it returns true, this value already appeared, so we return true.
• Otherwise, we call seen.add(num) and continue to the next number.

Because a HashSet lookup is constant on average, one pass through the array is enough. That single idea is what makes this approach shine.

7. Dry Run of the HashSet Approach

Watching the code run by hand makes it stick. Let us trace nums = [1, 2, 3, 1]. We follow the set as it grows.

Look at step four closely. We reach the second 1. The set already holds a 1 from step one. So the contains check returns true, and we stop right there. We never need to touch anything past that point.

7.1 The Same Dry Run on Paper

The sketch above shows the same trace. The array sits on top, the growing set sits on the right, and the arrow shows how the second 1 finds its earlier twin. Many people find this picture easier than the table, so use whichever clicks for you.

8. Comparing the Three Approaches

All three approaches give the correct answer. They just pay different prices. Here is the plain comparison.

In an interview, mention brute force first to show you understand the problem. Then bring up sorting as a smarter option. Finally, reach for the HashSet to show you can push to the best time complexity. That path from slow to fast is exactly what interviewers want to see.

9. Common Mistakes and Edge Cases

A few small traps catch beginners on this problem. Keep these in mind.

• An empty array or a single element has no duplicate, so the answer is false. All three approaches handle this naturally.
• With the sorting approach, remember that Arrays.sort changes the original array order. Copy the array first if the caller still needs it.
• In the HashSet version, always check contains before add. Swapping the order breaks the logic.
• Negative numbers and zeros work fine. Equality does not care about the sign of a number.

10. Interview Questions

11. Conclusion

The Contains Duplicate problem in Java looks like a warm-up, and it is. But the HashSet trick inside it is a real skill. You will reuse that same remember-as-you-go idea in many tougher array and string problems.

So take the lesson, not just the answer. Try brute force first to be safe. Reach for sorting when memory is tight. Then use a HashSet when you want the fastest single pass. Once that pattern feels natural, a whole family of problems opens up for you.

12. What’s Next

You now have Contains Duplicate in your toolkit, so let us keep the momentum going. Here is where you came from and where you head next in this series.

• Previous: Best Time to Buy and Sell Stock in Java — track the lowest price and the best profit in one pass.
• Next up: Maximum Subarray (Kadane’s Algorithm) — find the largest sum of any contiguous slice in a single sweep.

12. Further Reading

• LeetCode Contains Duplicate problem — practice the original problem and test your solution.
• Oracle Java HashSet documentation — the official reference for the class used here.