LESSON 236 OF 671 · SETS

Remove Repeats in Java: Keep the First Copy With a HashSet

You get an ArrayList of integers nums. Some values may appear more than once.

Return a new ArrayList that has each value only once.

Keep the first copy of each value and drop the later ones. The values stay in the order they first appear in nums.

Example 1:

Input: nums = [3, 1, 3, 2, 1]
Output: [3, 1, 2]
Explanation: The second 3 and the second 1 are repeats.
They are dropped, and 3, 1 and 2 stay in their order.

Example 2:

Input: nums = [6, 6, 6, 6]
Output: [6]
Explanation: Only the first 6 stays.

Example 3:

Input: nums = [4, 9, 2]
Output: [4, 9, 2]
Explanation: No value repeats, so every number stays.

Constraints:

nums has at least one number.
Every number is between -10⁹ and 10⁹.

STEP 1 OF 7

Guided

Ctrl + Enter to check

JAVA · SETS

Remove Repeats in Java, explained

Problem overview

The method removeRepeats receives a list of integers, nums, where some values may appear more than once. It returns a new list that has each value only once. The first copy of each value stays, later copies are dropped, and the values keep the order in which they first appear.

For [3, 1, 3, 2, 1] the result is [3, 1, 2]: the second 3 and the second 1 are repeats. For [6, 6, 6, 6] the result is [6]. For [4, 9, 2], where nothing repeats, every number stays.

Approach

Read the numbers from left to right and remember the ones already met in a HashSet. For each number, one question decides what happens: is it in the set yet? If not, it is a first copy, so it goes into the result list and into the set. If so, it is a repeat and is skipped.

Why not just use the set as the answer? A HashSet has no promised order, so it would lose the order the values first appeared in. The set only answers the question "seen already?"; the list keeps the order.

Step by step

Create an empty HashSet<Integer> named seen.
Create an empty List<Integer> named result, an ArrayList.
Loop over nums, with an int named num. Reading in order means the first copy of each value is the one that is kept.
Inside the loop, check that num is not in seen. The ! turns the answer of contains around.
Inside the if, add num to result.
Still inside the if, add num to seen, so the next copy is skipped.
After the loop, return result.

The solution in Java

class Solution {
    public List<Integer> removeRepeats(List<Integer> nums) {
        HashSet<Integer> seen = new HashSet<>();
        List<Integer> result = new ArrayList<>();
        for (int num : nums) {
            if (!seen.contains(num)) {
                result.add(num);
                seen.add(num);
            }
        }
        return result;
    }
}

The loop variable is an int, while the list and the set hold Integer objects. Java converts between the two automatically, so seen.contains(num) and result.add(num) work as they read. Equal values count as the same: a set of Integer compares by value, not by reference.

Tracing [3, 1, 3, 2, 1]: 3 is new and goes in; 1 is new and goes in; the second 3 is already in seen, so it is skipped; 2 is new and goes in; the second 1 is skipped. The result is [3, 1, 2].

Edge cases and common mistakes

Returning inside the loop. The return goes after the loop. Inside it, only the first value would come back.
Forgetting to add to seen. Without it, nothing is ever recognised as a repeat, and the result equals the input.
Adding to seen but not to result. The result stays empty.
Using the set as the result. The values could come out in a different order.

Testing

Running the solution on the three examples gives:

[3, 1, 2]
[6]
[4, 9, 2]

Java prints an ArrayList with square brackets and commas, as shown. The tests print the values separated by spaces.

One more case worth trying is a list that alternates, such as [1, 2, 1, 2]. The loop keeps the first 1 and the first 2, skips the other two, and returns [1, 2].

Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free