Contains Duplicate in Java DSA: From Brute Force to a One-Pass HashSet

Solve Contains Duplicate in Java DSA three ways — brute force, sort, and a one-pass HashSet — with full step-by-step dry runs and complexity comparison.

1. Introduction

Contains Duplicate in Java is one of those warm-up problems that hides a neat lesson. The question is tiny. You get an array, and you must say whether any value shows up more than once.

It sounds almost too easy. Return true if a number repeats, and false if every number is unique. That is the whole task.

But the fun part is how many ways you can solve it. We will build the answer in three steps, from slow to fast. First we brute force it with two loops. Then we sort the array and peek at neighbours. Finally we sweep once with a HashSet, which is the version interviewers want.

Every approach gets a full, step-by-step dry run. To keep it honest, we use a seven-number array that mixes positives and negatives: [4, -1, 2, 7, -1, 5, 3]. The value -1 sits at two spots, so this array has a duplicate.

We also trace a second array, [4, -1, 2, 7, 9, 5, 3], where every value is unique. That second run shows what happens when the answer is false and the loops go all the way to the end. Nothing is skipped in either run.

2. Understanding the Problem

Let us pin down the rules before we touch any code.

• You get an array of integers, like [4, -1, 2, 7, -1, 5, 3].
• Return true if any value appears at least twice.
• Return false if every value is different.
• The positions do not matter. Only the values matter.
• Negatives count too, so -1 and -1 are still a duplicate.

For our first array the answer is true, because -1 sits at index 1 and again at index 4. Swap that second -1 for a 9, and you get [4, -1, 2, 7, 9, 5, 3], where every value is unique and the answer is false. We will trace both.

3. Concepts You Need Here

3.1 What a Duplicate Really Means

A duplicate is just the same value seen twice at two different spots. So the real job is remembering what you have already seen. The moment a value shows up again, you have your answer.

3.2 The HashSet

A HashSet is a bag that holds only unique values. Add a number, and it either goes in fresh or the set tells you it was already there.

• Checking if a value is inside is very fast, close to instant on average.
• That speed is exactly what turns this into a clean one-pass solution.

4. Approach 1: Brute Force

Compare every number with every number after it. If any pair matches, you found a duplicate. It is slow, but it makes the goal crystal clear.

4.1 Pseudocode

for i from 0 to n-1:          // first number
    for j from i+1 to n-1:    // every number after i
        if nums[i] == nums[j]:
            return true       // found a repeat
 
return false                  // no repeats at all

4.2 Pseudocode Explained

• The outer loop picks one number at position i.
• Then the inner loop checks every number that sits after it.
• If two of them match, we return true right away.
• Should we finish both loops with no match, the array is clean, so we return false.

4.3 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 = { 4, -1, 2, 7, -1, 5, 3 };
        System.out.println(containsDuplicate(nums)); // true
    }
}

4.4 Java Code Explained

• Line 4 starts the outer loop on the first number.
• Next, line 5 walks j across everything after i.
• On line 6 we compare the two values.
• If they are equal, line 7 returns true and we stop.
• Reaching line 12 means no pair matched, so we return false.

4.5 Dry Run of the Brute Force – True Case

Array: [4, -1, 2, 7, -1, 5, 3]. The i index holds the first number, and j scans every number after it. We trace each comparison until one pair matches. The i (val) column shows the index and its value, and the same for j (val).

4.6 Reading the True Case

Let us walk each comparison and see what the loops are doing. The array is [4, -1, 2, 7, -1, 5, 3].

Steps 1 to 6: i is parked on 4. The outer loop fixes i at index 0, which holds 4. Now j sweeps every later slot to see if any equals 4.

• Step 1: j on -1. We ask 4 == -1, which is false. So j moves one step right.
• Next, step 2: j on 2. We ask 4 == 2, still false, and j moves on.
• At step 3: j on 7, then step 4: j on the second -1, then step 5: j on 5. None equals 4.
• Finally step 6: j on the last value 3. Again 4 == 3 is false. Now j has run off the end, so the inner loop stops and i moves right.

So the number 4 was compared against all six numbers after it and matched none. That is one full inner sweep with no luck.

Steps 7 to 9: i moves to the first -1. Now i sits at index 1, which holds -1. The j scan restarts from index 2.

• Step 7: j on 2. We ask -1 == 2, which is false.
• Then step 8: j on 7. Still -1 == 7 is false, so j keeps going.
• At step 9: j reaches index 4, the second -1. Now -1 == -1 is true. A duplicate. The method returns true and stops instantly.

Notice the loop never touched index 5 or 6. Once the first -1 found its twin, the search was over. The outer loop also never moved past index 1.

4.7 Dry Run of the Brute Force – False Case

Now the unique array [4, -1, 2, 7, 9, 5, 3]. Nothing repeats, so no pair ever matches. The loops must run all the way to the end and then return false. That is 21 comparisons in total, and we show every one.

4.8 Reading the False Case

Here nothing matches, so the loops grind through every pair. Watch how the block of comparisons shrinks as i moves right.

• Steps 1 to 6: i on 4, compared with all six later numbers. No match.
• During steps 7 to 11: i on -1, compared with the five numbers after it. No match.
• Then steps 12 to 15: i on 2, compared with the four after it. No match.
• At steps 16 to 18: i on 7, three comparisons, no match.
• Next, steps 19 to 20: i on 9, two comparisons, no match.
• Finally step 21: i on 5, just one comparison with 3. No match either.

Each time i moves right, its inner scan gets one step shorter, because j only ever looks at numbers after i. After the very last pair fails, both loops finish and the method returns false. That climb from six comparisons down to one is exactly the O(n²) shape.

4.9 Time and Space Cost

• Time is O(n²), because each number is compared with all the numbers after it.
• Space is O(1), since we store nothing extra.

Three comparisons for four numbers feels fine. But for a few thousand numbers this crawls, which is why we improve it next.

5. Approach 2: Sort First, Then Check Neighbours

Here is a smart trick. Sort the array, and any duplicates land right next to each other. Now you only need to compare each number with the one before it.

5.1 Pseudocode

sort nums
 
for i from 1 to n-1:
    if nums[i] == nums[i-1]:   // same as the neighbour before
        return true
 
return false

5.2 Pseudocode Explained

• Sorting pushes equal values side by side.
• Then one loop compares each number with its left neighbour.
• A match means a duplicate, so we return true.
• Finishing the loop with no match means every value is unique.

5.3 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 = { 4, -1, 2, 7, -1, 5, 3 };
        System.out.println(containsDuplicate(nums)); // true
    }
}

5.4 Java Code Explained

• Line 6 sorts the array in place.
• Next, line 7 starts the loop at index 1, not 0, so a left neighbour always exists.
• On line 8 we compare each value with the one just before it.
• A match makes line 9 return true.
• Falling out of the loop leads to false on line 13.

5.5 Dry Run of the Sort Approach – True Case

Original array: [4, -1, 2, 7, -1, 5, 3]. First the sort rearranges it, then the loop scans neighbours. We show both stages fully.

Stage 1 – the sort. Arrays.sort turns [4, -1, 2, 7, -1, 5, 3] into [-1, -1, 2, 3, 4, 5, 7]. The two -1s were far apart before, at index 1 and index 4. Now they sit side by side at index 0 and index 1.

Stage 2 – the neighbour scan. The loop starts at index 1 and compares each value with its left neighbour, nums[i-1].

The scan matched on its very first step, so the loop never reached index 2 or beyond. Sorting pulled the twin -1s to the front, so the check found them right away.

5.6 Reading the True Case

Stage 1: sorting does the heavy lifting. Before sorting, the duplicate -1s lived at index 1 and index 4, with 2 and 7 wedged between them. After Arrays.sort, the array becomes [-1, -1, 2, 3, 4, 5, 7]. Both -1s are now neighbours. This is the key move. Sorting turns a scattered search into a simple side-by-side check.

Stage 2, step 1: i at index 1. The loop begins at index 1 so that nums[i-1] is always safe to read. At i equals 1, the left neighbour nums[0] is -1 and the current value nums[1] is also -1. We compare them, they are equal, and the method returns true right away.

Because the match landed on the first comparison, the loop stopped there. The other five numbers were never even checked.

5.7 Dry Run of the Sort Approach – False Case

Now the unique array [4, -1, 2, 7, 9, 5, 3]. After sorting it becomes [-1, 2, 3, 4, 5, 7, 9]. Every neighbour pair is different, so the loop runs to the end and returns false. We trace all six comparisons.

5.8 Reading the False Case

Here the sorted array is [-1, 2, 3, 4, 5, 7, 9], climbing steadily with no repeats. The loop checks each value against the one on its left.

• Step 1: -1 vs 2 are different, so we continue.
• Then step 2: 2 vs 3, still different.
• At steps 3 to 5: 3 vs 4, then 4 vs 5, then 5 vs 7. Each pair differs.
• Finally step 6: 7 vs 9, different again. The loop has reached the last index, so it ends and the method returns false.

Because a sorted array places any duplicate side by side, one clean left-to-right scan is enough to be sure. No match in any neighbour pair means no duplicate anywhere.

5.9 Time and Space Cost

• Time is O(n log n), because sorting dominates the work.
• Space is O(1) extra if the sort works in place, though some sorts use a little more.

This beats brute force on large arrays. Still, sorting rearranges your data and costs that log factor, so the next version does better without touching order.

6. Approach 3: One-Pass HashSet

Walk the array once. Keep a HashSet of every value you have already seen. Before adding a number, ask the set whether it is already inside. If yes, that is your duplicate. This is the answer interviewers hope to see.

6.1 Pseudocode

seen = empty hash set
 
for each value v in nums:
    if v is already in seen:
        return true         // seen this one before
    add v to seen
 
return false                // finished with no repeat

6.2 Pseudocode Explained

• The set seen remembers every value we have passed.
• For each new value, we first check if it is already in the set.
• A hit means we saw it earlier, so we return true.
• Otherwise we drop it into the set and move on.

6.3 Java Code

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

6.4 Java Code Explained

• Line 7 creates an empty set to track seen values.
• Next, line 8 walks through each value v in the array.
• On line 9 we ask the set if v is already there.
• If so, line 10 returns true straight away.
• When it is new, line 12 adds v, and the loop continues.

6.5 Dry Run of the HashSet Approach – True Case

Array: [4, -1, 2, 7, -1, 5, 3]. We trace every value in order. Each row shows the set before the check, whether the value was already inside, the action taken, and the set after. The set starts empty. HashSet does not keep any order, so we list values in the order they went in only to make the trace easy to read.

6.6 Reading the True Case

Let us go value by value and watch the set decide each step. The array is [4, -1, 2, 7, -1, 5, 3].

• Step 1: v is 4. The set is empty, so 4 is not inside. We add 4, and seen becomes { 4 }.
• Next, step 2: v is -1. The set holds { 4 }, and -1 is not there. We add -1, so seen is { 4, -1 }. This first -1 is the one we will catch later.
• At step 3: v is 2. The set holds { 4, -1 }, and 2 is missing. We add 2, and seen grows to { 4, -1, 2 }.
• Then step 4: v is 7. Not in the set either, so we add it. Now seen is { 4, -1, 2, 7 }.
• Finally step 5: v is -1 again. We ask if -1 is in the set, and it is, from step 2. So the method returns true at once.

So the loop stopped at step 5 and never looked at 5 or 3. That second -1 found the first -1 already waiting in the set, which is the whole trick.

One timing rule makes this work. We always check the set before we add the current value. That is why a lonely value can never wrongly match itself, and why the repeat is caught only when its twin arrives.

6.7 Dry Run of the HashSet Approach – False Case

Now the unique array [4, -1, 2, 7, 9, 5, 3]. No value repeats, so the check never hits, and every value gets added. The loop finishes all seven steps and returns false.

6.8 Reading the False Case

This time no value is ever a repeat, so each step just grows the set by one.

• Steps 1 to 4: 4, then -1, then 2, then 7. None was seen before, so each gets added.
• During steps 5 and 6: 9 and 5 arrive, both new, both added.
• Finally step 7: 3 is checked, found new, and added. The array is now exhausted.

After the last value, the loop ends with no match found, so the method returns false. Notice the set ends with all seven values inside. When the answer is false, the HashSet approach touches every element exactly once, which is its O(n) behaviour.

6.9 Comparing the Three Traces

7. The Dry Run on Paper

Tables are exact, but a sketch often lands faster. Here is the same HashSet true-case trace drawn by hand.

• Each navy box shows a fresh value being added to the set.
• The green box marks the repeated -1 that triggers the match.
• At the bottom, the finished answer reads true.

8. Comparing the Three Approaches

All three give the same answer. They just pay different prices.

The HashSet version wins on speed, at the cost of some memory for the set. The sort version saves memory but pays the log factor and shuffles your array. Brute force stays simple yet slow.

In an interview, start with brute force, point out the wasted second loop, then jump to the HashSet and explain the one-pass check. That climb is the story interviewers want to hear.

9. Common Mistakes and Edge Cases

A few small traps catch beginners on Contains Duplicate. Keep them in mind.

• Adding the value before the check makes every number match itself, so always check first.
• Starting the sort-approach loop at index 0 reads nums[-1] and crashes, so begin at index 1.
• An empty array or a single element has no possible duplicate, so it should return false.
• Very large arrays can hold values that repeat far apart, which is exactly where the HashSet shines.

Run the empty and single-element cases through your code before you call it done. They catch more bugs than any ordinary input will.

10. Interview Questions

11. Conclusion

Contains Duplicate in Java looks trivial, and in a way it is. Yet it teaches a habit you will reuse everywhere.

Our seven-number traces showed the payoff clearly. Brute force compared pairs until it stumbled on a match, or ground through all 21 pairs when nothing repeated. Sorting pulled the twin -1s together first. The HashSet remembered what it had seen and caught the repeat in a single pass.

So take the pattern, not just the answer. When a problem asks “have I seen this before?”, reach for a set. That one idea unlocks a huge pile of array and string problems waiting further down the list.

12. Further Reading

• LeetCode Contains Duplicate problem — practice the original problem and submit your own solution.
• Oracle Java HashSet documentation — the official reference for the HashSet used in the optimal approach.
• Previous in this series: Best Time to Buy and Sell Stock in Java — track the lowest price so far to find the best single-day profit.
• Next in this series: Maximum Subarray in Java — use Kadane’s algorithm to find the largest sum in one pass.

javahandson.com | DSA Series | Arrays & Strings