Learn

You keyed your set on an int array, and the same pair is counted twice

7 November 2026 · One mistake, one counterexample

The hard part of a hash map question is usually choosing the key. You chose it, a pair of numbers, and wrote it down as the most natural thing Java offers for two numbers. The sample passes. Then the interviewer adds one repeated row and your count goes up by one.

The situation

A log of flights arrives as rows of two airport ids, from and to. The question is how many different routes the log contains. A set is the obvious tool:

static int distinctRoutes(int[][] flights) {
    Set<int[]> routes = new HashSet<>();
    for (int[] f : flights) {
        routes.add(f);
    }
    return routes.size();
}

The sample has three rows and three different routes, so the answer is three and the test is green. Nothing in that sample checks whether two equal rows become one entry.

The input that breaks it

Call it with {{1, 2}, {1, 2}, {2, 1}}. You expect 2: the route from 1 to 2 appears twice, and 2 to 1 is a different route. You get 3.

The reason is what a Java array means by "equal". Arrays do not override equals or hashCode, so they inherit the versions from Object, which compare identity. Two arrays holding the same numbers are two objects, so the set sees two different keys. One line proves it: new int[]{1, 2}.equals(new int[]{1, 2}) prints false, while Arrays.equals on the same two arrays prints true. The set calls the first one.

The same key in a memo is worse, because it fails quietly. A recursion with two parameters, memoised in a Map<int[], Long>, never finds an entry it stored, since every lookup builds a new array. The answers stay correct. The memo simply never hits, so the solution runs at the speed of the plain recursion and times out on the large test, which looks like a complexity problem rather than a key problem.

Python gives you a louder version: putting a list in a set raises TypeError: unhashable type, and you switch to a tuple. The quiet version in Python is a small class of your own:

class Route:
    def __init__(self, src, dst):
        self.src, self.dst = src, dst

print(len({Route(1, 2), Route(1, 2)}))  # 2, not 1

Without __eq__ and __hash__, a class compares by identity, exactly like the Java array.

The hidden assumption is two keys holding the same values are the same key. That is only true if the key's type says so.

The fix and the invariant

Give the key a type that compares by value. In Java a record does this for you:

record Route(int from, int to) {}

static int distinctRoutes(int[][] flights) {
    Set<Route> routes = new HashSet<>();
    for (int[] f : flights) {
        routes.add(new Route(f[0], f[1]));
    }
    return routes.size();
}

On the same input the two Route(1, 2) values are equal and hash alike, so the answer is 2. List.of(f[0], f[1]) works too. In Python, @dataclass(frozen=True) on the class above makes the set hold one route.

There is a second half to the invariant. A key must not change after it goes in. Put an ArrayList holding 1 and 2 into a HashSet, add 3 to that list, and contains on the same list prints false: the set filed it under the old hash.

The invariant to say: two keys that describe the same thing are equal and hash alike, and no key changes once it is in the map.

What to say out loud

When you write the key, say: "I'm keying on a record of the two ids, so equal routes are equal keys. An int array would compare by identity and every lookup would miss." It costs five seconds and shows the interviewer you know what the map does with your key.

If the count is already wrong, name the input first: "The same route twice, counted twice. So my set doesn't think they're equal. My key is an array, and arrays compare by identity." Then change the one type. Saying the cause before the fix shows a diagnosis, not a guess.

The exercise

1. Search your last ten practice solutions for Set<int[]>, Map<int[], and Python classes you put in a set or used as a dictionary key.
2. For each one, write down what the smallest input with two equal keys should return, then run it and compare.
3. Find a memoised recursion you wrote with two parameters. Predict, before running it, whether its memo ever hits, and check by counting stored entries against lookups.
4. Write the three-line ArrayList example from the section above and predict what contains prints before you run it.
5. In your next practice problem, say the key sentence aloud as you declare the map.

Where this fits in Gadfly

Gadfly has four rooms, and in the algorithms room you code in Java or Python. In tutor mode it asks the next question instead of revealing the solution, so "what does your set compare when it checks a pair?" is the kind of question it would ask when a count comes out one too high. "I'm stuck" gives one more step, up to pseudocode, never finished code.