What is the time complexity of HashMap.containsValue() in java?

To answer the question in the title – as mentioned by others, containsValue is O(n), because without the key it doesn’t know where it is and the algorithm has to go over all the values stored in the map.

To answer the question in the body of your question – on how to solve it – just consider whether you really need a general map which can count how many instances have you seen of each number. I mean, the only time you’d care if there’s more than one appearance of a number is when it’s x/2, right? That smells like a corner case to me. Just add a test that checks for that corner case – something like embedding if (numberList[i] == requiredSum/2) half++ during your set-construction loop, and then if (requiredSum % 2 == 0 && half == 2) return true after it (see other variation below).

Then you can just iterate over the set and for each item check whether requiredSum-item also appears in the set.

To summarize (with early exits when possible):

Set<Integer> seen = new HashSet<Integer>();
boolean halfSeen = false;
for (int num : numberList) {
    if (num == requiredSum/2 && requiredSum % 2 == 0) {
        if (halfSeen) return true;
        halfSeen = true;
    } else {
        seen.add(num);
    }
}
for (int num : seen) {
    if (seen.contains(requiredSum - num)) return true;
}
return false;

Leave a Comment